[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)，每个左括号最多进一次栈出一次栈，代码如下：

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

view raw Longest Valid Parentheses.cpp hosted with ❤ by GitHub