LeetCode32 最长有效括号

题目描述

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

样例

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

算法分析

思路很难想

• 有效括号,左右括号数量相等
• 任意前缀左括号数量大于右括号数量

思路来源小呆呆

• 若当前栈为空 或者 当前元素是'('，则直接加入栈中

• 当当前元素是')'时，说明有和栈顶元素匹配的可能

• 匹配

• 栈不为空，弹出 stk.pop(),再更新ans = Math.max(ans, i - stk.peek())
• 栈空,ans = Math.max(ans, i + 1)；
• 栈顶元素不能和’)’匹配，则直接加入到栈中

时间复杂度$O(n)$

Java代码

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stk = new Stack<Integer>();
        int ans = 0;
        for(int i = 0; i < s.length(); i++){
            char t = s.charAt(i);
            if(stk.isEmpty() || t == '(') stk.push(i);
            else{
                if(s.charAt(stk.peek()) == '('){
                    stk.pop();
                    if(!stk.isEmpty()) ans = Math.max(ans, i - stk.peek()); //栈不空
                    else ans = Math.max(ans, i+1); //如果栈空就是 i+1
                }else{
                    stk.push(i);
                }
            }
        }

        return ans;
    }
}