60 最长有效括号

题目描述

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

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

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

示例 3：
输入：s = ""
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13

题解1 DP+stack

class Solution {
public:
    int longestValidParentheses(string s) {
        int st = s.size();
        if(0 == st) return 0;
        stack<int> stk;
        vector<int> dp(st+1, 0);

        for(int i = 0; i < st; i++){
            if(s[i] == '('){
                stk.push(i);
                // 如果是左括号说明i位置不会有效，对应在dp里i+1位置置零即可
                dp[i+1] = 0;
            }else{
                if(! stk.empty()){
                // 如果没有stack，递推公式稍微复杂一点
                // key：别忘了+dp[stk.top()]
                // 以防迷惑：stk.top()是最近的左括号下标值，dp[stk.top()+1]=0
                    dp[i+1] = i + 1 - stk.top() + dp[stk.top()];
                    stk.pop(); 
                }else dp[i+1] = 0;
            }
                
        }
        int ret = INT_MIN;
        for(auto& i : dp){
            ret = max(ret, i);
        }
        return ret;
    }
};
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
28
29
30
31

题解2 stack

class Solution {
public:
    int longestValidParentheses(string s) {
        int st = s.size();
        if(0 == st) return 0;
        stack<int> stk;
        // 处理第一个字符是左括号的情况
        stk.push(-1);
        int ret = 0;
        for(int i = 0; i < st; i++){
            if(s[i] == '('){
                stk.push(i);
            }else{
                // 遇到右括号，先弹栈（遇到右括号，前面的连续有效括号就作废了）
                stk.pop();
                if(! stk.empty()){
                    ret = max(ret, i-stk.top());
                }else {
                    stk.push(i);
                }
            }
                
        }
        return ret;
    }
};
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

题解3 DP

class Solution {
public:
    int longestValidParentheses(string s) {
        int st = s.size();
        if(0 == st) return 0;
        vector<int> dp(st, 0);
        int maxS = 0; 
        for(int i = 1; i < st; i++){
            if(s[i] == ')'){
            // "()()"
                if(s[i-1] == '('){
                    dp[i] = 2;
                    // 前面还有项（如果有stack就会马上定位到上一个有效序列的开始）
                    if(i >= 2)
                        dp[i] = dp[i-2] + dp[i];
                }
            	// "(())"
                else if(dp[i-1]){
                
                    if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '('){
                        dp[i] = dp[i-1] + 2;
                        // 前面还有项
                        if(i - dp[i-1] - 2 >= 0)
                            dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                    }    
                }                    
            }
            maxS = max(maxS, dp[i]);
        }
        return maxS;
    }
};
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
28
29
30
31
32

题解4 左右指针

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxlength = 0;
        // 左扫
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        // 右扫：解决左扫扫不出来的"(((()"
        for (int i = (int)s.length() - 1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
};
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
28
29
30
31
32
33
34