题目：
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 global_longest = ;
int last_not_match = -;
stack<int> sta;
for ( int i = ; i < s.length(); ++i )
{
if ( s[i]=='(')
{
sta.push(i);
continue;
}
if ( s[i]==')')
{
if ( sta.empty() )
{
last_not_match = i;
}
else
{
sta.pop();
if ( sta.empty() )
{
global_longest = std::max( global_longest, i-last_not_match );
}
else
{
global_longest = std::max( global_longest, i-sta.top() );
}
}
}
}
return global_longest;
}
};
tips：
这里巧用堆栈，核心是堆栈里存放的不是字符本身而是字符所在的索引值。
额外再用一个变量保存上一次没有匹配的字符的索引值。
每次更新global_longest的时候，都判断堆栈是否清空：
1. 如果堆栈清空了，则证明直到last_not_match之前的都是有效的字符串，所以完整有效长度为i-last_not_match
2. 如果堆栈没有清空，则说明还有‘(’没有被匹配上，所以临时有效长度i-sta.top()
这里设定last_not_match初始值为-1，主要是考虑如果从第一个元素就包含在有效范围内的test case （如，“()”）
=======================================
此题还有DP的解法，但总感觉DP解法思路不太直观，怪怪的。
留一个看过的DP解法的blog，以后有时间再研究
http://bangbingsyb.blogspot.sg/2014/11/leetcode-longest-valid-parentheses.html
=========================================
第二次过这道题，一开始写了一个动态规划的算法：逻辑可能是对的，但是绝对超时。
还是强化记忆了一下stack的做法：巧用栈的特点，O(n)复杂度搞定。
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> sta;
int ret = ;
int last_not_match = -;
int i=;
while ( i<s.size() )
{
if ( s[i]=='(' )
{
sta.push(i);
}
else
{
if ( sta.empty() )
{
last_not_match = i;
}
else
{
sta.pop();
if (sta.empty())
{
ret = max(ret,i - last_not_match);
}
else
{
ret = max(ret, i - sta.top());
}
}
}
++i;
}
return ret;
}
};