LeetCode hot100-90

https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

32. 最长有效括号
已解答
困难
相关标签
相关企业
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
子串
的长度。

动态规划的分析看着太复杂了，这题最经典的应该是用栈来做吧。感觉这题就是个模版，需要背一下那种。

核心思想
使用一个栈来存储索引：
栈中的元素表示未匹配的括号的索引。
通过索引，我们可以计算出当前有效括号的长度。
初始化时，向栈中放入 -1：
-1 是一个“哨兵”值，用来帮助计算从字符串开始位置的有效括号长度。
遍历字符串，进行以下操作：
如果当前字符是 ‘(’，将其索引入栈。
如果当前字符是 ‘)’，弹出栈顶：
如果栈为空，说明当前括号无法匹配，将当前索引入栈，作为新的“起点”。
如果栈不为空，计算当前有效括号的长度（当前索引 - 栈顶索引），并更新最大长度。

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