32. Longest Valid Parentheses

题目

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

大意

找到可以匹配的最长的括号串.

答案

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

思路

栈中保存的不是字符（而是字符（所在的下标。
如果遇到字符（，无条件压入栈中；
如果遇到字符），并且栈为空，说明这是一个无法匹配的字符），用变量last记录下标。last存放的其实是最后一个无法匹配的字符）。
如果遇到字符），并且栈不为空，我们可以消除一对括号（栈顶元素出栈）。

• 如果栈为空，用当前元素下标i 减去 last计算有效长度；
• 如果栈不为空，用当前元素下标i 减去 栈顶元素下标计算有效长度；