Leetcode 32. 最长有效括号

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

1. 示例

1.1 示例1

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

1.2 示例2

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

1.3 示例3

输入：s = ""
输出：0

2. 方法

2.1 动态规划

大多数涉及到求最值的问题我们都可以使用动态规划的方法求解。我们定义 dp[i] 表示以下表i字符结尾的最长有效括号的长度，由于题目要求括号连续，因此有效的子串一定以')'结尾，故以'('结尾的字符串对应的值一定为0。

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 (s[i-1] == ')' && i > dp[i-1] && s[i - 1 - dp[i-1]] == '(')
                    dp[i] = dp[i-1] + (i > dp[i-1] + 1 ? dp[i - 2 - dp[i-1]] : 0) + 2;
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

2.2 栈

我们始终保持栈底元素为最后一个没有被匹配的')'（注意是栈底，不是栈顶）。我们从左到右遍历字符串，将碰到的每个'('的下标加入栈中。当碰到')'时，我们弹出一次栈顶。如果pop操作后栈不空，则说明匹配到了'('，否则当前的')'即为最后一个没有被匹配的右括号，我们加入它的下标到栈中。若匹配到了左括号，则开始计算当前有效括号的长度，即用当前字符下标减去栈顶元素下标。

注意：最开始栈为空时，若第一个字符为'('，则不满足我们关于栈底元素为最后一个没有被匹配的右括号的定义。因此最开始加入-1作为栈底元素。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), 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;
    }
};

2.3 贪心

在前面我们提到，由于有效括号要求连续，则只有当碰到')'时才会进行长度的计算，因此我们使用两个变量分别统计碰到的左右括号的数量，由于左括号要在前面，因此当右括号的数量大于左括号时，我们重置计数器，相等时，有效括号的数量即为2倍的计数器的数量。
但这样做会忽略一种情况：如果左括号的数量总是比右括号的数量多，则我们无法进行有效长度的计算。如例子：(()。
这时，我们可以倒序遍历字符串，还是统计二者的数量，不同的是，当碰到左括号比右括号数量多时，我们对计数器进行清零，同样的，二者相等时进行长度的计算。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), ans = 0;
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') ++l;
            else ++r;
            if (l == r) ans = max(ans, 2 * r);
            else if (r > l) l = r = 0;
        }
        l = r = 0;
        for (int i = n-1; ~i; --i) {
            if (s[i] == '(') ++l;
            else ++r;
            if (l == r) ans = max(ans, 2 * l);
            else if (l > r) l = r = 0;
        }
        return ans;
    }
};