LeetCode: Longest Valid Parentheses

思路分析

这道也是把人卡爽的题目，网上有一堆相对复杂的思路，但是实际上可以利用括号匹配用栈描述的性质，写出非常简洁漂亮的解。首先我们知道如何利用栈来判断括号是否匹配，那么如果我们在栈的每一个元素中同样记录一下这是字符串中第几个字符，这样等出栈时，当前的位置减去出栈之后的栈顶中保存的位置，即为可以用来更新最大长度的值。因为当前已经处理完一个匹配括号序列了，我们通过这种方式获得的是这个序列的长度。

注意由于如果整个序列恰好完全匹配，那么显然会在栈空时还要访问栈顶，为了避免这种情况，我们令初始时栈不为空，即随便添加进去一个字符，而位置为零即可。这种记录元素的同时记录位置信息的想法，可以用来解决很多常见问题，比如一些BFS可以很漂亮地写出来。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<pair<char, int> > stk;
        int res = 0;
        stk.push(make_pair(')', 0));
        for ( int i = 0; i < s.length(); i++ ) {
            if ( s[i] == '(' ) {
                stk.push(make_pair(s[i], i + 1));
            } else if ( s[i] == ')' ) {
                if ( stk.top().first == '(' ) {
                    stk.pop();
                    res = max(res, i + 1 - stk.top().second);
                } else {
                    stk.push(make_pair(')', i + 1));
                }
            }
        }
        return res;
    }
};