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

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

示例 2： 输入：s = ”)()())”

输出：4 解释：最长有效括号子串是 ”()()”

示例 3： 输入：s = "" 输出：0

---

先做一个热身题

20. 有效的括号

给定一个只包括 ’(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。  

示例 1：

输入：s = ”()” 输出：true 示例 2：

输入：s = ”()[]{}” 输出：true 示例 3：

输入：s = ”(]” 输出：false 示例 4：

输入：s = ”([)]” 输出：false 示例 5：

输入：s = ”{[]}” 输出：true  

使用栈的方法

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        stack = []
        pair = {
            '(': ')',
            '[': ']',
            '{': '}',
        }
        for i in range(len(s)):
            if s[i] in pair.keys():
                stack.append(s[i])
            elif s[i] in pair.values():
                # 可能只有右括号
                if stack:
                    p = stack.pop()
                else:
                    return False
                if pair[p] != s[i]:
                    return False
            else:
                return False
        # 如果还有多余的左括号，表示不合规
        return not stack

C++版本

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1){
            return false;
        }
        unordered_map<char, char> pair = {
            {')', '('},
            {'}', '{'},
            {']', '['},
        };
        stack<char> stk;
        for (char ch: s){
            if (pair.count(ch)){
                if (stk.empty() || stk.top() != pair[ch]){
                    return false;
                }
                stk.pop();
            }else{
                stk.emplace(ch);
            }
        }
        return stk.empty();
    }
};

最长有效括号

动态规划

记dp[i]为以序号i结尾的最长有效括号的长度。则有以下几种情况：

• 以(结尾的串肯定不合法，直接赋0
• 以)结尾的串，分两种情况：
  • 如果s[i-1]为(, 则dp[i] = dp[i-2] + 2
  • 如果s[i-1]为), 且dp[i-1]是一个有效的括号段，且这个括号段前一个元素是(, 则dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2

时间复杂度和空间复杂度均为O(n)

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        int ans = 0;
        for (int i = 1; i < n; i++){
            if (s[i] == ')'){
                if (s[i-1] == '('){
                    dp[i] = (i > 2 ? dp[i-2] : 0) + 2;
                }else if (i > dp[i-1] && s[i-dp[i-1]-1] == '('){
                        int part1 = i-dp[i-1] > 2 ? dp[i-dp[i-1]-2] : 0;
                        dp[i] = dp[i-1] + part1 + 2;
                    }
            }
            ans = max(ans, dp[i]);
        }
        // for(auto i : dp){
        //     cout << i << " ";
        // }
        return ans;
    }
};

栈的方法

保持栈顶元素为当前最后一个没有被匹配的右括号的下标。

若为左括号，则将其序号入栈 若为右括号，则先弹出栈顶元素，然后判断：

• 若栈为空，则将当前i入栈
• 不为空，计算i-s.top()则为以该右括号结尾的最大有效括号的长度

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int ans = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < n; i++){
            if (s[i] == '('){
                stk.push(i);
            }else{
                stk.pop();
                if (stk.empty()){
                    stk.push(i);
                }else{
                    ans = max(ans, i-stk.top());
                }
            }
        }
        return ans;
    }
};

两趟遍历

不是很好理解，或者说有点巧妙

用两个计数器left和right分别记录左括号和右括号的个数。两次扫描

1. 先从左到右扫描，

   • 如果left与right相等, 记录差值
   • 如果left < right, 计数器清零

2. 从右到左扫描，

   • 如果left与right相等, 记录差值
   • 如果left > right, 计数器清零

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        // cout << s.size() << " " << s.length() << endl;
        int ans = 0;
        int left = 0, right = 0;
        for (int i = 0; i < n; i++){
            if (s[i] == '('){
                left += 1;
            }else{
                right += 1;
            }
            if (left < right) {
                left = 0;
                right = 0;
            }
            if (left == right){
                ans = max(ans, right*2);
            }
        }

        left = right = 0;
        for (int i = n-1; i>0; i--){
            if (s[i] == '('){
                left += 1;
            }else{
                right += 1;
            }
            if (left > right) {
                left = 0;
                right = 0;
            }
            if (left == right){
                ans = max(ans, right*2);
            }
        }
        return ans;
    }
};