[LeetCode]Longest Valid Parentheses

我们用stack记录左右左括号的位置，同时维护left边界对应stack为空的情况，每次对应的操作如下：

• 如果stack为空，且当前字符s[i]为右括号，left = i + 1，continue。因为从任何i左边的字符开始经过i的string都是不是valid parentheses了。
• 如果当前字符为左括号，stack.push(i)，记录对应坐标
• 如果当前字符为右括号，pop栈顶元素
• 如果此时stack为空，那么以s[i]结尾的最长valid parentheses的长度len为i - left + 1
• 否则，len = i - stack.top()

我们不断更新maxlen即可。每一次pop栈顶的元素的时候，我们都是找的当前右括号结尾的最长valid parentheses，假设栈不为空的话，那么栈顶元素对应的就是最右边的没有match的左括号，其右边的直到i为止都是valid的。假设栈为空，那么代表没有未被match的左括号，从left开始直到i的序列都是valid的。

空间复杂度O(n)，时间复杂度O(n)，每个左括号最多进一次栈出一次栈，代码如下：