32. 最长有效括号（高频题）

32. 最长有效括号

• 解题思路
• 代码

解题思路

有关括号匹配的问题一般都用栈。

我们扫描到左括号，就将当前位置入栈。
扫描到右括号，就将栈顶出栈（代表栈顶的左括号匹配到了右括号），然后分两种情况。

• 栈不空，那么就用当前的位置减去栈顶的存的位置，然后就得到当前合法序列的长度，然后更新一下最长长度。

• 栈是空的，说明之前没有与之匹配的左括号，那么就将当前的位置入栈。

代码

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        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 = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}