Monthly Archives: June 2016

LeetCode Longest Valid Parentheses

LeetCode 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.


此题要求一个括号字符串中最长的合法的括号串的长度。
遇到括号问题,想当然的用栈来解决,可以尝试每一个以'('开头的字符串,用栈求出其最长合法括号串的长度,然后求全局最大值,如下:

class Solution {
public:
	int longestValidParentheses(string s) {
		int n = s.size(), maxval = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '(') {
				stack<char> sc;
				sc.push(s[i]);
				int cur = 0;
				for (int j = i + 1; j < n; j++) {
					char t = sc.top();
					if (s[j] == ')') {
						if (t == '(') {
							sc.pop();
							cur++;
						}
						else
							break;
					}
					sc.push(s[j]);
				}
				if (cur > maxval)maxval = cur;
			}
		}
		return maxval * 2;
	}
};

但是这个算法是O(n^2)的,TLE。
后来看题解,居然有O(n)的解法,厉害,如下:

class Solution {
public:
	int longestValidParentheses(string s) {
		int n = s.size(), maxval = 0, start = -1; // start初始化为-1
		stack<int> si;
		for (int i = 0; i < n; i++) {
			if (s[i] == '(') {
				si.push(i); //左括号无条件压栈
			}
			else { //右括号不压栈
				if (si.empty()) {
					start = i; //以右括号作为新的起点
				}
				else {
					si.pop();
					if (si.empty()) // ()()() or (()())
						maxval = max(maxval, i - start);
					else // (() 用当前栈顶索引作为起点
						maxval = max(maxval, i - si.top());
				}
			}
		}
		return maxval;
	}
};

本算法提交AC,用时12MS。
它也是用堆栈,但是堆栈里存的不是括号,而是括号的索引。左括号无条件压栈,右括号不压栈,只是作为计算括号对的长度的起点(其实起点应该是右括号索引+1,但是计算长度的时候用右括号索引更方便)。
所以栈里面只有左括号,当右括号来了,且栈为空时,说明之前已经配对完了,要开始新的配对,所以设置新的起点。
如果栈不为空,则pop。如果pop完之后栈为空,也说明配对完成,可以更新最佳长度;如果pop完之后栈里还有左括号,则是(((()这种类型,左括号更多,则匹配的起点应该是栈顶的索引,而不是之前设置的右括号索引+1,如下:

 (((()
^  ^