题目原型：
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.
思路一：
使用栈的方式。
时间复杂度 O(n)，空间复杂度 O(n)
public int longestValidParentheses(String s)
{
int countMax = 0;
int start = -1;
Stack
stack = new Stack
(); for(int i = 0;i
(i-start) countMax:(i-start); } else { countMax = countMax>(i-stack.get(stack.size()-1)) countMax:(i-stack.get(stack.size()-1)); } } } } return countMax; }
思路二：
使用动态规划
时间复杂度 O(n)，空间复杂度 O(n)
基本思路：
以"("为中心
如果出现了"("那么就分以下几种情况：
1、立即与后面的")"匹配，如：()
2、与后面的第N个")"匹配，如：(((...)))
3、不匹配如：(,(()[表示match>=len]
public int longestValidParentheses(String s)
{
int len = s.length();
int[] flag = new int[len];
int match = 0;
int result = 0;
for(int i = len - 2;i>=0;i--)
{
match = i+1+flag[i+1];
//处理((...))的情况
if(s.charAt(i)=='('&&match
flag[i] result:flag[i];
}
return result;
}
思路三：（类似思路一）
两遍扫描
时间复杂度 O(n)，空间复杂度 O(1)
为什么要扫描两遍？
就是因为防止出现"(()"的情况，在扫第一遍的时候，返回值是0，因为depth是不会等于0的，result无法赋值，但是第二遍扫描的时候就不同了，返回2.
public int longestValidParentheses(String s)
{
int len = s.length();
int depth = 0;
int start = -1;
int result = 0;
//从前往后扫
for(int i = 0 ;i
(i-start) result:(i-start);
}
}
}
depth = 0;
start = s.length();
for(int i = len - 1;i>=0;i--)
{
if(s.charAt(i)==')')
{
depth++;
}
else
{
--depth;
if(depth<0)
{
start = i;
depth = 0;
}
else if(depth==0)
{
result = result>(i-start) result:(start-i);
}
}
}
return result;
}