最长有效括号

最长有效括号

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

提示：

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

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> st = new Stack<Integer>();
        int ans = 0;
        for(int i = 0 ,start = 0;i < s.length();i ++)
        {
            if( s.charAt(i) == '(') st.add(i);
            else
            {
                if(!st.isEmpty()) 
                {
                    st.pop();
                    if(st.isEmpty()) ans = Math.max(ans,i - start + 1);
                    else ans = Math.max(ans,i - st.peek());
                }
                else start = i + 1;
            }
        }
        return ans;
    }
}

具体过程如下：

• 用栈维护当前待匹配的左括号的位置，同时用 start 记录一个新的可能合法的子串的起始位置，初始设为0。

• 如果s[i] ==’(‘，那么把i进栈。

• 如果s[i] == ‘)’,那么弹出栈顶元素 （代表栈顶的左括号匹配到了右括号），出栈后：

如果栈为空，说明以当前右括号为右端点的合法括号序列的左端点为start，则更新答案 i - start + 1。

如果栈不为空，说明以当前右括号为右端点的合法括号序列的左端点为栈顶元素的下一个元素，则更新答案i - st.top() 。

• 遇到右括号)且当前栈为空，则当前的 start 开始的子串不再可能为合法子串了，下一个合法子串的起始位置是 i + 1，更新 start = i + 1。

• 最后返回答案。

实现细节： 栈保存的是下标。

复杂度分析

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

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

---

作者：LeetCode-Solution
链接：32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。