32. 最长有效括号

题目描述

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

示例 1：

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

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：

输入：s = “”
输出：0

提示：

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

---

做题思路

• 这个题目一开始我想到是用栈来处理，但是我做着做着发现自己想的太简单了，很多点 都没有考虑全面

• 于是看了官方的题解…😔

• 当遇到左括号将下标直接放入栈中

• 当遇到右括号时先取出栈顶元素

  ：此时如果栈为空，将这个右括号的下标放入栈中

  如果栈不为空，那么计算有效长度

  官方题解用了一种很巧妙的方法

  始终保持栈顶元素为不匹配的右括号的下标

  利用这个性质我们就可以方便的求出最大长度了

• 还有一点需要注意：刚开始的时候我们需要将 (-1) 添加到栈中，来模拟这个不匹配的右括号的下标

代码实现

class Solution {
    public int longestValidParentheses(String s) {
        if(s==null)return 0;
        int n=s.length();
        if(n==0)return n;
        Deque<Integer> q=new ArrayDeque<>();
        int max=0;
        q.push(-1);
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            if(c=='('){
                q.push(i);
            }else{
                q.pop();
                if(q.isEmpty()){
                    q.push(i);
                }else{
                    max=Math.max(max,i-q.peek());
                }
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目链接

32. 最长有效括号