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.

1.【基础知识】
压栈、弹栈机制能够很好的模仿括号配对。

2.【屌丝代码】

完成失败！

达成思想：

1）字符串截取，取到第一个‘(‘为字符串首元素；

2）字符串的元素小于等于1，合法长度判断为0；

3）依次查找每一个正括号为首元素最长合法长度；

卡壳部分：

1）未能实现每一个正括号为首元素的最长合法长度计算！

3.【AC源码】

// LeetCode, Longest Valid Parenthese
// 使用栈，时间复杂度 O(n)，空间复杂度 O(n)
class Solution {
	public:
		int longestValidParentheses(string s) {
			int max_len = 0, last = -1; // the position of the last ')'
			stack<int> lefts; // keep track of the positions of non-matching '('s
			for (int i = 0; i < s.size(); ++i) {
				if (s[i] =='(') {
						lefts.push(i);
					} 
				else {
					if (lefts.empty()) {
						// no matching left
						last = i;
					} 
					else {
						// find a matching pair
						lefts.pop();
						if (lefts.empty()) {
							max_len = max(max_len, i-last);
						} 
						else {
							max_len = max(max_len, i-lefts.top());
						}
					}
				}
			}
		return max_len;
	}
};

1）脑子没想好就不要动手写代码，写代码也是信马由缰毫无效率，思路不成熟的上手，在有限时间内，对任务的完成只会徒增恐惧感与无助感；

2）对于一个没想清楚的问题，去反问一句这是不是关键问题，如果是，就把它想透再下手！

比如本例：最相近的两个符号找到之后，它们是不是一定成对，如果成对接下去是怎么办？之前和止呕的操作分别是什么？！坚决将这个问题的求解出来的态度是伟大光荣而正确的！

LeetCode 之 Longest Valid Parentheses

原文：http://blog.csdn.net/u013630349/article/details/47016773