32. Longest Valid Parentheses

發表於 | 分類於

problem

solution

option 1

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
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> sta;
        int start = 0, ret= 0;
        for(int i=0;i<s.size();++i){
            char c= s[i];
            if(c=='('){
                sta.push(i);
            }
            else{
            
                if(sta.empty()) start = i+1;
                else{
                    sta.pop();
                    if(sta.empty()) ret = max(i-start+1, ret);
                    else ret = max(ret, i- sta.top());
                        
                }
                
            }
        }
        return ret;
    }
};

option 2 - dp

option 3 - Two Pointers , reduce dp