Leetcode 32: Longest valid parentheses

Leetcode 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.

找出最长的有效（）对， 一开始对这个题目没有思路，最先想到的是找最长的（）对，用dp来做，但是dp的做法想到的是对输入的字符串一点点分，判断有没有（）对，有多长。 其实这个题目很巧妙，不需要用dp来做，对于valid parentheses的判断，用stack来做就好，回头看前面的元素是否匹配，怎么记录消掉的长度，这题很巧妙的地方在于存在stack里面的是char的index，而不是char，一开始想的是存char，如果正好匹配就消除并且记录长度，但是这样记录长度很麻烦，存index就很方便了，每次消掉一对消掉的长度可以用current index - index in the top of the stack来记录，每次消掉就update max的值，当然要注意stack为empty时的一些判断。

class Solution {
public:
    int longestValidParentheses(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        stack<int> st; //stack stores the index of the chars
        //when (), update the length, the current index - top element in stack
        int max_len = 0;
        for (int i = 0; i < s.size(); i++) {
            if (st.empty()) st.push(i);
            else if (s[st.top()] == '(' && s[i] == ')') { //match, update max_len
                st.pop();
                if (!st.empty()) max_len = max(max_len, i - st.top());
                else max_len = max(max_len, i+1);
            }else {
                st.push(i);
            }
        }
        return max_len;
    }
};