LeetCode刷题【32】最长有效括号

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

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

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

输入：s = ""
输出：0

栈模拟，java

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int idx = -1;
        int ans = 0;
        while (++idx < s.length()) {
            //表示上一个未被匹配的左括号'('
            if (s.charAt(idx) == '(') {
                stack.push(idx);
            } else {
                //这里是右括号‘)’
                stack.pop();
                if (!stack.isEmpty()) {
                    ans = Math.max(ans, idx - stack.peek());
                }else{
                    stack.push(idx);
                }
            }
        }
        return ans;
    }
}

1. 栈底元素是有效区间的起始位置
2. 之后栈内只插入左括号（的位置
3. 每遇到一个右括号，则从栈顶弹出一个元素
4. 如果弹出的是左括号，那么就能知道当前的有效区间的长度
5. 如果弹出的右括号，此时栈内为空，之前的有效区间不存在了，后面再能遇到的是新的有效区间，需要从当前位置重新开始表示，那么就把当前值插入到栈底部
6. 在每次得到有效区间的时候，依次比较取较大值