最长有效括号（dp/栈/计数）

题目：https://leetcode-cn.com/problems/longest-valid-parentheses/ 参考了官方orz dp做法： d p [ i ] dp[i] dp[i]表示前 i i i个字符能得到的最大长度

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector dp;
        dp.resize(n+1);
        int ans = 0;
        for(int i = 1;i = 2 ? dp[i-2] : 0) + 2;
                else if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '(')
                    dp[i] = dp[i-1] + (i-2-dp[i-1] >= 0 ? dp[i-2-dp[i-1]] : 0) + 2;
                ans = max(ans,dp[i]);
            }
        }
        printf("%d\n",ans);
        return ans;
    }
};

栈做法

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        stack st;
        int ans = 0;
        st.push(-1);
        for(int i = 0,x;i  
        
       
         r 
        
       
      
        l>r 
       
      
    l>r的情况，如 
     
      
       
       
         ( 
        
       
         ( 
        
       
         ( 
        
       
         ) 
        
       
         ) 
        
       
      
        ((()) 
       
      
    ((())，而这确是从右到左遍历会考虑到的。这两种遍历相辅相成，考虑了所有的情况。
 
class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        int l = 0,r = 0;
        int ans = 0;
        for(int i = 0;i  r) l = r =0;
        }
        printf("%d\n",ans);
        return ans;
    }
};