Leetcode 棧 Longest Valid Parentheses

Leetcode 棧 Longest Valid Parentheses

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.

題意：給定一個包含括號 '(',')'的字符串，返回最長匹配的括號數目
思路1：棧
用一個變量_max表示當前最長匹配的括號數
不存右括號，只存左括號的index。掃描一遍字符串，
如果當前的字符是'('，則壓棧
如果當前的字符是')'，則
1.若棧空，則當前的')'沒有一個'('與它匹配，它可以作用它左右兩個匹配的括號串的分割點，用一個變量 last 記錄下它的坐標。
last的初始值是-1，當遇到新的分割點時，我們更新 last，並可以得到兩個 last之間的匹配括號的長度
2.若棧非空，則當前的')'與棧頂的'('匹配
將棧頂元素出棧
如果此時棧為空，則找到了一組匹配括號串，更新 _max = max(_max, last - i)
如果此時棧不空，則棧頂的'('還沒找到它的')'，因為棧頂元素有可能找不到它的')'，因此，此時要更新 _max = max(_max, i - stack.top())

復雜度：時間O(n)，空間O(n)

int longestValidParentheses(string s){
	int _max = 0, last = -1;
	stack left;
	for(int i = 0;  i < s.size(); ++i){
		if(s[i] == '(') left.push(i);
		else{
			if(left.empty()) last = i;
			else{
				left.pop();
				if(left.empty()){
					_max = max(_max, i - last);
				}else{
					_max = max(_max, i - left.top());
				}
			}
		}
	}
	return _max;
}