$$\color{Red}{最长有效括号【leetcode32 栈】}$$

下面的链接是——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

解析

这道题看似是个困难，但是有了前面几个括号题的熏陶，说实话这道题只需要理解一个新的点，即：当出现一个不合法的序列的情况，视为枚举这段的开头到当前位置的下一个位置【因为当前不合法只能是右括号，下一段肯定不可能让一个右括号当第一个元素，开局就非法了】算一段。

其实看到分段，几乎就能意识到我想说什么了，即一个合法的括号序列，肯定不能横跨每段的分界线。

反证法

假设一个合法的括号序列横跨了一个边界。那么我们假设这个边界把这个合法括号序列分成两部分，一部分在边界左边，可以看作在左边界内的段中的一段区间。【称之为左截断区间】

那么我们知道这段左区间所在的段，一定满足，右括号的数量大于左括号，那么 左截短区间 作为其中的一部分，也只能满足这个性质。

但是

一个合法的括号序列的任意前缀，一定得满足左括号的数量严格大于等于右括号的数量，故和假设矛盾。即开局的定理成立

那么我们就在每段内部去找合法的括号序列即可省去不停移动位置的尴尬。

• 如果出现左括号无脑放入栈。

• 如果出现右括号栈空即非法，划分下一段。

• 栈不空则弹出，两者相结合。
  • 如果此时栈还有括号，那么当前段内的一个合法区间就是当前栈顶元素的右边第一个位置到目前枚举的右括号的区间。
  • 如果没括号了，说明从当前段的一个位置到现在括号的位置都是合法的，取这段为当前一个合法答案。

不断更新最大的答案，即求出最大值。

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