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

解题思路：最容易想到的解法就是穷举法，计算任意两点(i到j)之间有多少个合法的()串，借助动态规划可以得到结果。算法复杂度为：O(n³)。

　　用栈来解决明显可以减小时间复杂度，但是这里入栈的是元素的索引，这样用于求最长匹配的括号长度。在程序中设置一个匹配起点ptstart用于保存当前匹配的起点，用mxlength来保存当前的匹配最大长度。

　　每次来了‘(’之后，无条件压栈。如果碰到')'的话，如果栈不为空，就消除栈内栈顶的'('
　　1.消除掉'('之后，如果栈内还有剩余的‘(’的话，最长的合法长度就是：maxlength = max(i - stack.top() , maxlength);  也就是取：当前')'的index减去栈顶元素的index  和 原来max_length 两者的最大值。

　　　　例如：对于这种情况：()(()()，可以正确的得出最大值为4。

　　2.消除掉')'之后，栈内没有剩余的‘(’了。此时需要引入一个新的变量ptstart，用于表示合法括号字符串的起点。

　　　　例如：对于这种情况：())()()，可以正确的得出最大值为4。
　　start初始为-1，之后每次碰到‘)’且栈为空的时候更新为当前‘)’的index。也就是说无法消除的)之后的括号不可能再和前面的括号合并在一起计算最长序列，所以更新start。

c++代码：

#include <iostream>
#include <string>
#include <stack>
using namespace std;
class Solution {
public:
    int longestValidParentheses(string s) {
		int maxlength = 0;
		int len = s.length();
		int i;
		int ptstart = -1;
		stack<int> st;
		for(i = 0; i < len; i++){
			if(s[i] == '('){
				st.push(i);
			}
			if(s[i] == ')'){
				if(st.empty()){
					ptstart = i;
				}else{
					st.pop();
					if(st.empty()){
						maxlength = max(i-ptstart, maxlength);
					}else{
						maxlength = max(i-st.top(),maxlength);
					}
				}
			}
		}
        return maxlength;
    }
};

int main(){
	Solution s = Solution();
	string test = "(()(()";
	int r = s.longestValidParentheses(test);
	cout << r << endl;
	return 0;
}