首页 > 代码库 > LeetCode Longest Valid Parentheses

LeetCode Longest Valid Parentheses

class Solution {public:    int longestValidParentheses(string s) {        vector<int> stack;        int maxlen = 0;        int curlen = 0;        int last = -1;        int len = s.length();        for (int i=0; i<len; i++) {            char ch = s[i];            if (ch == () {                stack.push_back(i);                continue;            }            if (stack.empty()) {                last = i;                continue;            }            stack.pop_back();            if (stack.empty()) {                curlen = i - last;            } else {                curlen = i - stack.back();            }                        if (curlen > maxlen) maxlen = curlen;        }                return maxlen;    }};

参考:http://www.cnblogs.com/zhuli19901106/p/3547419.html

last用来记录最后一个无法匹配的右括号的位置,当stack为空时,必然存在一个合法的括号序列,而这个序列的起始肯定是last后面的一个位置。

智商有限,做了好久,只有看答案了。。。