最长有效括号

Posted on Edited on Symbols count in article: 3.2k Reading time ≈ 3 mins.

32 最长有效括号

方法1：动态规划

1.1 错误1

无法解决诸如(())的问题。 要考虑到当前碰到右括号后，前面的是左括号还是右括号，然后分别进行处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int l = 0;
        vector<int> dp(n);
        int ret = 0;
        for(int i=0; i<n; ++i){
            if(s[i] == '('){
                ++l; 
                continue;
            }
            if(l){
                --l;
                dp[i] = 2;
                if(i-2 >= 0) dp[i] += dp[i-2]; // BUG
                ret = max(ret, dp[i]);
            }
        }
        return ret;
    }
};

1.2 错误2

无法解决诸如()(())的问题。

  1. *****() 好解决直接 dp[i] += dp[i-2];
  2. *****)) 需要额外判断找到与当前右括号i对应的左括号t，然后t的左边要继续判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int l = 0;
        vector<int> dp(n);
        int ret = 0;
        for(int i=0; i<n; ++i){
            if(s[i] == '('){
                ++l; 
                continue;
            }
            if(l){
                --l;
                dp[i] = 2;
                if(s[i-1] == '(' && i-2 >= 0) dp[i] += dp[i-2];
                else if(s[i-1] == ')') dp[i] += dp[i-1]; // 这里要继续修改
                ret = max(ret, dp[i]);
            }
        }
        return ret;
    }
};

1.3 正确答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        int l = 0;
        vector<int> dp(n);
        int ret = 0;
        for(int i=0; i<n; ++i){
            if(s[i] == '('){
                ++l; 
                continue;
            }
            if(l){
                --l;
                dp[i] = 2;
                if(s[i-1] == '(' && i-2 >= 0) dp[i] += dp[i-2];
                else if(s[i-1] == ')'){
                    dp[i] += dp[i-1];
                    if(i-dp[i]>=0) //添加这里
                        dp[i] += dp[i-dp[i]];
                }
                ret = max(ret, dp[i]);
            }
        }
        return ret;
    }
};

1.4 官方的DP（LC官方）(Elegant)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        int res = 0;
        for(int i=1; i<n; ++i){
            if(s[i] == '(') continue;
            // 只有以')'结尾的才有效
            if(s[i-1] == '('){
                if(i-2 < 0) dp[i] = 2; // 防止越界
                else dp[i] = dp[i-2] + 2; // 转移函数
            }else{
                if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1] == '('){
                    dp[i] = dp[i-1] + 2; // 转移函数
                    if(i-dp[i-1]-2 >= 0)
                        dp[i] += dp[i-dp[i-1]-2];
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

方法2：栈（LC官方）

保持栈底元素为当前已经遍历过的元素中 「最后一个没有被匹配的右括号的下标」 需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 -1−1 的元素。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        stack<int> stk;
        stk.push(-1);
        int res = 0;
        for(int i=0; i<n; ++i){
            if(s[i] == '(') stk.push(i);
            else{
                stk.pop();
                if(stk.empty()) // 更新「最后一个没有被匹配的右括号的下标」
                    stk.push(i);
                else
                    res = max(res, i-stk.top()); // 以i结尾的有效性括号长度
            }
        }
        return res;
    }
};

方法3：贪心（LC官方）

利用两个计数器l和r，从左到右遍历字符串，遇到左括号则l加1，遇到右括号则r加1；当l和r相等时更新最长长度，当r>l时将l和r置0

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。

解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：当r<l时将l和r置0。

这样我们就能涵盖所有情况从而求解出答案。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestValidParentheses(string s) {
        int l = 0, r = 0;
        int res = 0;
        for(int i=0; i<s.size(); ++i){
            if(s[i] == '(') ++l;
            else ++r;
            if(l == r) res = max(res, l + r);
            else if(r > l) l = r = 0;
        }
        l = r = 0; // 重置！
        for(int i=s.size()-1; i>=0; --i){
            if(s[i] == '(') ++l;
            else ++r;
            if(l == r) res = max(res, l + r);
            else if(l > r) l = r = 0;
        }
        return res;
    }
};