题解 | #最长的括号子串#

双指针，正反（一个合法断里面的前缀or后缀）

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

DP

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> f(s.size()+1, 0);
        int ans = 0;
        for (int i = 1; i < s.size(); i ++){
            if(s[i] == '(') continue;

            if(s[i-1] == '(') f[i] = (i>=2 ? f[i-2] : 0) + 2;
            else if(s[i-f[i-1]-1] == '(') f[i] = f[i-1] + (i-f[i-1]-2>=0?f[i-f[i-1]-2]:0) + 2;
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

栈（加一个特殊值卡住每一段）

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> stk; stk.push_back(-1);
        int ans = 0;
        for(int i = 0; i < s.size(); i ++){
            if(s[i] == '('){
                stk.push_back(i);
            }else {
                if(stk.size() == 1){
                    stk.pop_back();
                    stk.push_back(i);
                }else {
                    stk.pop_back();
                    ans = max(ans, i - stk.back());
                }
            }
        }
        return ans;
    }
};