力扣(LeetCode)32. 最长有效括号(C++)

栈模拟

合法的括号序列满足两条性质：
1.左括号数等于右括号数
2.任意前缀里，左括号数大于等于右括号数。

括号匹配和栈很般配，遇到左括号，下标入栈，遇到右括号，弹栈匹配。
这题的前缀里有两种不合法，一种是左括号特别多，右括号不够，这种情况以右括号数主导合法括号数。另一种是任意前缀，右括号数大于左括号数，这种情况以左括号数主导合法括号数。

提示 : 从起点开始，当连续序列的右括号数大于左括号数，那么连续序列的合法括号数达到最大值，要从连续序列的下一个位置开始，才可能遇到新的合法序列。

对于上述问题做归一化处理，请看代码。

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int ans = 0;
        for(int i = 0,start = -1;i<s.size();i++){
            if('('==s[i]) stk.push(i);
            else{
                if(stk.size()){
                    stk.pop();
                    if(stk.size()) ans = max(ans,i-stk.top());//左括号较多，匹配
                    else ans = max(ans,i - start);//左括号紧缺，匹配
                }else start = i;//起点总是慢合法区域一步
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1. 时间复杂度 : $O(n)$ ， 字符串 $s$ 的长度是 $n$ ，一次遍历 $s$ 括号匹配的时间复杂度 $O(n)$。
2. 空间复杂度 : $O(n)$ ， 栈的最坏空间复杂度 $O(n)$ 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，答主看到就会回复的。

AC