leetcode32题解之最长有效括号

最开始看这道题的时候觉得直接按照有效字符串的思路去做就可以了，但是一直wa，后来发现这东西需要像最大矩形那道题目一样，需要记录一个起始点的下标的栈，然后根据pop的时候，设置相应规则进行迭代， 代码如下

点击(此处)折叠或打开

1. int longestValidParentheses(string s){
   
2.     stack<int> st;
   
3.     int start=-1, len=s.length();
   
4.     int res=0;
   
5.     for(int i=0; i<len; i++){
   
6.         if(s[i]=='(')st.push(i);// 左括号下标入栈，防止算多
   
7.         else{
   
8.             if(st.empty())start=i;// 弹出非法才会更新start
   
9.             else{
   
10.                 st.pop();
    
11.                 if(st.empty())res=max(res,i-start);// 为空，则(start,i]满足全匹配
    
12.                 else res=max(res,i-st.top());// 若不为空，则(st.top,i]满足全匹配
    
13.             }
    
14.         }
    
15.     }
    
16.     return res;
    
17. }