最长的括号子串（栈）

题意

给一个只包含左右括号的字符串，求其中正确匹配子串的最大长度。

思路分析

正确的括号匹配

如果题目给的括号序列是正确的,如(())，或者检查是否是正确的

那么匹配过程是

遇到左括号，把左括号压入栈中
遇到右括号，把左括号顶部的移出栈中

注意到栈中只会存左括号，于是可以简化为记录数量即可

int cnt = 0;
for(auto ch:s){
    if(ch == '(')cnt++; // 计数+1
    else if(ch == ')'){
        if(cnt == 0)return false; // 匹配失败
        cnt --; // 匹配一个
    }
}
return cnt == 0; // 完全匹配

已经匹配的统计

对于上面的匹配过程，还想记录未被匹配的括号之间的已匹配的个数

例如 (()(()(( 希望记录为0(2(2(0(0，如图

因为是数字和左括号间隔，所以数字个数减1就是左括号个数，只用记录数字即可

alt

每次放入(，就是放入了(0，也就是数字放入了零

每次放入), 就是让最后的...A(B变成了...A+B+2

因此每次只会处理末尾的值，可以用一个栈来维护

vector<int> arr = {0}; // pair between left brace
for(auto ch:s){
    if(ch == '('){
        arr.push_back(0);
    }else if(ch == ')'){
        if(arr.size() == 1){ // no left brace
            arr = {0};
        }else{
            arr[arr.size()-2] += arr.back()+2;
            arr.pop_back();
        }
    }
}

边界处理

初始化时，只有数字0

对于放入右括号而没有左括号时，因为它无法和任何匹配，所以和初始化同样操作

统计最大值

按照上面的操作，剩下来的左括号，都是无论如何无法在正确匹配中被匹配的，也就是它们隔断了正确匹配的子串，所以每次遇到右括号合并时，更新最大值

ans = max(ans,stack.back());

题解

将上面的逻辑联系起来

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        // write code here
        int ans = 0; // max
        vector<int> arr = {0}; // pair between l brace
        for(auto ch:s){
            if(ch == '('){
                arr.push_back(0);
            }else if(ch == ')'){
                if(arr.size() == 1){
                    arr = {0};
                }else{
                    arr[arr.size()-2]+=arr.back()+2;
                    arr.pop_back();
                    ans = max(ans,arr.back());
                }
            }
        }
        return ans;
    }
};

复杂度分析

空间复杂度 : 最大是全为左括号，记录了所有之间的值， $O (n)$

时间复杂度 : 遍历时，每次计算是常数代价，所以总时间复杂度为 $O (n)$

题解 | #最长的括号子串#