Leetcode No.32 最长有效括号

一、题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"

示例 3：

输入：s = "" 输出：0

提示：

0 <= s.length <= 3 * 104 s[i] 为 '(' 或 ')'

二、解题思路

从左往右扫描，已扫描的左括号等待被匹配，用一个栈暂存起来。 题目是求长度，存左括号的索引即可，没必要存符号本身。 当扫描到右括号，它匹配「最近一个」左括号，栈顶被匹配而出栈，有效长度 = 当前索引-出栈的索引+1，并挑战一下全局的最大 如图，当遍历到索引为 6 的右括号时，此时栈中的左括号匹配光了，但左边有一整段长度为 6 的有效子串，让索引 6 减 0？不对。或许让 5 减 -1？

修改思路 在栈中预置 -1 作为一个“参照物”，并改变计算方式：当前索引 - 出栈后新的栈顶索引。

当遍历到索引 5 的右括号，此时栈顶为 2，出栈，栈顶变为 -1，有效长度为 5 - (-1) = 6。如果像之前那样，5 找不到 -1 减。 当遍历到索引 6 的右括号，它不是需要入栈的左括号，又匹配不到左括号，怎么处理呢？ 它后面可能也出现这么一段有效长度，它要成为 -1 那样的“参照物”。它之前出现的有效长度都求过了，-1 的使命已经完成了，要被替代。 所以我们照常让 -1 出栈。不同的是，此时栈空了，让索引 6 入栈当 “参照物”。 总结：两种索引会入栈 等待被匹配的左括号索引。 充当「分隔符」的右括号索引。因为：当左括号匹配光时，栈需要留一个垫底的参照物，用于计算一段连续的有效长度。

三、代码

package longestValidParentheses;

import java.util.Stack;

class Solution {
    public int longestValidParentheses(String s) {
        int max=0;
        Stack<Integer> stack=new Stack();
        stack.push(-1);
        int rs=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.empty()){
                    stack.push(i);
                }else{
                    max=Integer.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }
    public static void main(String[] args) {
        Solution solution=new Solution();
        int rs=solution.longestValidParentheses(")()())()()(");
        System.out.println(rs);
    }
}

四、复杂度分析

时间复杂度： O(n)，n是给定字符串的长度。我们只需要遍历字符串一次即可。

空间复杂度： O(n)，栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n)。