力扣---最长有效括号---动态规划，栈

动态规划思路：

最长xxxx的问题，从动态规划的角度去考虑，我们会将 g[i] 定义为以 第 i 位 结尾的小问题。在本道题中，我们将 g[i] 定义为以第 i 位为结尾的最长有效括号子串的长度。从头去遍历每一位，我们会发现只有s[i]为‘ ）’才有资格当结尾。那么就分为以下两种情况：第一种情况为...()，那么递推公式为g[i]=g[i-2]+2，第二种情况为...))，...|.......)|)，我们将子串分为3部分，其中中间那部分的长度为g[i-1]，这个时候如果第i位的加入可以得到更好的答案（也就是s[i-1-g[i-1]]='('），那么递推公式为g[i]=g[i-1]+2+g[i-2-g[i-1]]，为什么还要加上g[i-2-g[i-1]]？因为还要加上能和第二部分连接上的第一部分子串。数组初始化即为g[i]=0。

代码：

C++：

class Solution {
public:
    int longestValidParentheses(string s) {
        int res=0;
        int len=s.size();
        vector<int> g(len,0);  //以第 i 位为结尾的最长有效括号子串的长度
        for(int i=1;i<len;i++){
            if(s[i]==')'){//‘）’才可以，分为两种情况，第一种是....()，第二种是....))
                if(s[i-1]=='('){ //第一种情况
                    if(i-2<0){
                        g[i]=2;
                        res=max(res,g[i]);
                    }
                    else{
                        g[i]=g[i-2]+2;
                        res=max(res,g[i]);
                    }
                }
                else{ //第二种情况
                    if(i-g[i-1]-1>=0 && s[i-g[i-1]-1]=='('){
                        if(i-g[i-1]-2>=0){
                            g[i]=g[i-1]+2+g[i-g[i-1]-2];
                            res=max(res,g[i]);
                        }
                        else{
                            g[i]=g[i-1]+2;
                            res=max(res,g[i]);
                        }
                    }
                }
            }
        }
        return res;
    }
};

Python：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res=0
        len_s=len(s)
        g=[0]*len_s
        for i in range(1,len_s):
            if s[i]==')':
                if s[i-1]=='(':
                    if i-2<0:
                        g[i]=2
                        res=max(res,g[i])
                    else:
                        g[i]=g[i-2]+2
                        res=max(res,g[i])
                else:
                    if i-g[i-1]-1>=0 and s[i-g[i-1]-1]=='(':
                        if i-g[i-1]-2>=0:
                            g[i]=g[i-1]+2+g[i-g[i-1]-2]
                            res=max(res,g[i])
                        else:
                            g[i]=g[i-1]+2
                            res=max(res,g[i])
        return res

栈思路：

首先，将所有匹配的左括号和右括号的索引全都记录下来（此时不考虑连续），将这些索引记录到一个数组中，然后再进行最长连续索引的判断。

代码：

C++：

class Solution {
public:
    int longestValidParentheses(string s) {
        int len=s.size();
        deque<int> q; //记录左括号下标
        vector<int> res;

        for(int i=0;i<len;i++){
            if(s[i]=='('){
                q.push_back(i);
            }
            else{
                if(!q.empty()){ //记录这一对下标
                    int temp=q.back();
                    q.pop_back();
                    res.push_back(i);
                    res.push_back(temp);
                }
            }
        }
        if(res.empty()){return 0;}
        //对res进行排序，找最长连续子串
        sort(res.begin(),res.end());
        int len_res=res.size();
        int cnt=1;
        int fin=0;
        for(int i=1;i<len_res;i++){
            if(res[i]==res[i-1]+1){
                cnt++;
            }
            else{
                fin=max(fin,cnt);
                cnt=1;
            }
        }
        fin=max(fin,cnt);
        return fin;
    }
};

Python：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        len_s=len(s)
        q=deque()
        res=[]
        for i in range(len_s):
            if s[i]=='(':
                q.append(i)
            else:
                if q:
                    temp=q[-1]
                    q.pop()
                    res.append(i)
                    res.append(temp)
        if len(res)==0:
            return 0
        res.sort()
        len_res=len(res)
        cnt=1
        fin=0
        for i in range(1,len_res):
            if res[i]==res[i-1]+1:
                cnt+=1
            else:
                fin=max(fin,cnt)
                cnt=1
        fin=max(fin,cnt)
        return fin

注意，对列表的排序代码：（在原列表上直接修改）

res.sort()

同时，因为用到了deque，所以需要库：

from collections import deque