leetcode 32. 最长有效括号

题目描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0
提示：
0 <= s.length <= 3 * 10⁴
s[i] 为 ‘(’ 或 ‘)’

分析

一道hard难度的括号匹配问题，一个只包含一类括号的括号序列合法，当且仅当其左括号数量等于右括号数量，并且任意前缀中左括号数量不小于右括号数量。我们使用一个计数变量，遇见左括号就++，右括号就–，很容易判断以某个下标开头的序列是不是合法的，但是本题需要找最长合法的括号序列的长度。

一个合法的括号序列可以细分为几类：

• 并列式：(A) + (B)，也就是几个合法括号序列连接起来。
• 包含式：((A)(B))，在几个合法括号序列外加上了括号。

不使用栈模拟

用一个例子来模拟下括号匹配的过程：
（）（（））（））（（（）)

遍历第一个左括号，cnt++，第二个cnt–，此时cnt为0，表示从开始到当前遍历到的括号是一个合法的括号序列，但是不能保证是以第一个左括号开头的最长的合法序列，因为后面可能还有并列的合法序列存在。

继续遍历发现后面四个字符也能构成一个合法序列，遍历到第6个字符时，cnt再次回到0 ，此时从开头的左括号能够延伸到的合法括号序列最长也是到第6个字符。

继续遍历之后的1个左括号，cnt = 1，后面遇见右括号，cnt = 0，此时最长括号序列的长度扩展到了8，但是之后又来了个右括号，使得cnt = -1，右括号前面没有与之匹配的左括号，加上这个右括号序列就不合法了，所以前面合法的括号序列不能继续延伸，后面即使有并列的合法括号序列也与前面的括号序列无关了，所以出现负数的cnt就相当于一个分隔信号。

继续遍历到例子中的最后一组括号序列，由三个左括号和两个右括号构成，遍历结束时cnt = 1，由于只在cnt = 0时更新最长括号序列的长度，所以最后一段序列中合法序列的长度没有统计上。

通过这个例子的模拟我们可以发现，使用计数变量来模拟，遇见cnt归零就更新最长序列的长度，遇见cnt为负数就清空前面累计的合法序列的长度。如果不考虑最后一段左括号数大于右括号数的序列的话，所求的的最长合法序列长度就是前面那段的最长合法序列长度。

再来看最后一段括号序列，其合法子序列是最后的四个字符(())，而遍历到倒数第四个字符时cnt = 2，不是什么特别的数，所以我们无法确定这个序列中最长合法括号序列的左端点是哪里，或者说只有从右边倒着遍历才能找到左端点在哪。

对于最后一段括号序列的特殊情况，有两种处理方式。正着遍历一遍括号序列后，倒着再遍历下，遇见右括号cnt++，左括号cnt–，同样是遇见cnt = 0更新最长序列长度，遇见cnt < 0清空累计的最长序列长度；另一种处理方式是正着模拟下括号序列，然后把括号序列翻转后左右括号互换，再正着遍历下括号序列，效果和第一种方式是一样的，好处是可以复用正着遍历的代码。

不使用栈模拟的代码如下：

class Solution {
    
public:
    int count(string &s){
    
        int len = 0,cnt = 0,ans = 0;
        for(int i = 0;i < s.size();i++){
    
            if(s[i] == '(') cnt++;
            else    cnt--;
            len++;
            if(!cnt)    ans = max(ans,len);
            else if(cnt < 0)    cnt = len = 0;
        }
        return ans;
    }
    int longestValidParentheses(string s) {
    
        int ans = count(s);
        reverse(s.begin(),s.end());
        for(int i = 0;i < s.size();i++){
    
            if(s[i] == '(') s[i] = ')';
            else    s[i] = '(';
        }
        ans = max(ans,count(s));
        return ans;
    }
};

栈模拟

不使用栈模拟我们已知的信息只有cnt和len，需要在cnt < 0时来更新最长合法序列的起点。对于一般的括号匹配问题，使用栈模拟的做法是遇见左括号就入栈，右括号就出栈，如果遍历过程中需要出栈时栈非空并且遍历完成后栈空说明该括号序列合法。栈模拟的缺点是需要额外的空间，好处是每次左括号出栈时都是遇见了与之匹配的右括号，这便于我们统计括号序列的长度。回忆下不用栈进行模拟之所以要遍历两遍，就是因为括号序列的最后一部分我们可能无法确定与最右边右括号配对的左括号的位置，而使用栈模拟就不会有这种顾虑了。对于合法的括号序列中的每个右括号，我们一定能找到与之配对的左括号；找不到与之配对的左括号，那么这个右括号一定不是合法括号序列中的一员。

我们使用栈再来模拟下上面的例子（可以在纸上模拟下这个过程，便于理解）
（）（（））（））（（（）)

我们先将一个哨兵节点-1入栈，为什么要使用哨兵节点，后面再解释。

遍历第一个左括号，将其下标入栈，因为入栈的都是左括号，所以没必要保存字符，保存下标便于我们统计序列的长度。遍历第二个字符右括号，遇见右括号就可以出栈了，此时合法括号序列的长度应该就是2，而当前右括号下标1减去现在栈顶元素-1恰好就是2。

遍历第二部分的括号序列，两个左括号入栈，遍历到第五个字符右括号，栈顶元素出栈，此时遍历到右括号的下标是4，新的栈顶元素的下标是2，也就是与当前右括号配对的上一个左括号的位置，4 - 2 = 2，也就是以当前右括号为末尾的最长合法括号序列的长度。继续遍历下一个右括号，栈顶的左括号出栈，此时栈里还剩最先入栈的哨兵节点-1，当前右括号的下标5，减去-1等于6，也就是以当前右括号为末尾的最长合法括号序列的长度。

遍历第三部分括号序列，前两个字符遍历过程和上面一样，左括号入栈，右括号时栈顶元素出栈，更新以当前元素为末尾的最长合法括号序列的长度。当遍历到下一个右括号时，栈里只有哨兵节点-1了，出栈后也不会与右括号匹配，此时就不需要更新解了，但是需要将当前右括号入栈作为新的哨兵节点，这里的哨兵节点指示的是新一段合法括号序列左端点的前一个位置，所以需要在一开始将-1入队。如果后面还有右括号，就继续出栈入栈，这样可以保持哨兵节点始终是后面的右括号。

遍历第四部分括号序列，三个左括号入栈，然后两个右括号时出栈，更新解。这时可以注意到，遍历到最后一个右括号时，栈顶元素是与之配对的左括号，需要及时出栈，新的栈顶元素就是与之配对的左括号的上一个字符的下标，两个字符下标相减就可以更新解了。

栈模拟算法的正确性在于，我们遍历括号序列时必然会遍历到每个右括号，栈顶元素就是与之配对的左括号，栈顶元素出栈后新的栈顶元素如果是左括号就说明这个左括号还没有遇见与之匹配的右括号，以当前遍历到的右括号为末尾的合法括号序列只能向左延伸到与之配对的左括号位置了；如果新的栈顶元素是哨兵节点（栈里只剩下一个元素就是哨兵），说明这个右括号与之匹配的左括号之前的括号序列也已经是匹配的了，哨兵节点的位置就是这部分合法括号序列起点的上一个位置，也就可以求出完整的合法括号序列的长度了。

这种问题代码往往不复杂，难度之一在于需要考虑到所有的情况，比如使用的例子需要包含并列括号的情况，不合法的括号序列情况以及最后一部分括号序列左括号数大于右括号数的情况；另一个难点在于对于右括号找到与之匹配的左括号后，要根据栈里的情况进行判断，看这次配对的括号序列能不能向左延伸，以及巧妙的使用哨兵节点来记录新的合法的括号序列开头位置的上一个位置。

使用栈模拟的代码如下：

class Solution {
    
public:
    int longestValidParentheses(string s) {
    
        vector<int> stk;
        stk.push_back(-1);
        int res = 0;
        for(int i = 0;i < s.size();i++){
    
            if(s[i] == '(') stk.push_back(i);
            else{
    
                stk.pop_back();
                if(!stk.size()) stk.push_back(i);
                else    res = max(res,i - stk.back());
            }
        }
        return res;
    }
};