32. Longest Valid Parentheses

problem description

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

algorithm thought

括号匹配问题就是用栈解决，这里其实也存在括号匹配，所以首先考虑用栈解决。这题比括号匹配需要多考虑的一个点就是如果右括号多了的话，需要重新开始记录，因为后面的肯定和前面的括号不能连在一起了。所以这里需要特殊考虑。

我首先自己写了一个双栈的代码，一个记录之前匹配好的括号的值，一个是记录左右括号括号的。但是后面看了discuss发现其实用一个栈就行，每次直接一次匹配完当前合法的，也就是右括号没多的情况。如果右括号多了，就改变一下start pos

code

//use two stack
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st1;
        st1.push(0);
        stack<char> st2;
        int res=0;
        for(auto ch:s){
            if(ch=='('){
                st1.push(0);
                st2.push(ch);
            }else{
                if(st2.empty()){
                    st1.push(0);
                }else{
                    st2.pop();
                    int tmp=st1.top();
                    st1.pop();
                    tmp+=2;
                    tmp+=st1.top();
                    st1.pop();
                    res=max(res,tmp);
                    st1.push(tmp);
                }
            }
        }
        return res;
    }
};

//use one stack
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int startpos=-1;
        int res=0;
        for(int i=0;i<s.size();++i){
            if(s[i]=='('){
                st.push(i);
            }else{
                if(st.empty())
                    startpos=i;
                else{
                    st.pop();
                    if(st.empty()){
                        res=max(res,i-startpos);
                    }else{
                        res=max(res,i-st.top());
                    }
                }
            }
        }
        return res;
    }
};

algorithm analysis

不管是使用两个栈还是一个栈，时间复杂度都是O(n),但是一个栈的方法明显好很多。