题目原型：
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<Integer> stack = new Stack<Integer>();
for(int i = 0;i<s.length();i++)
{
char ch = s.charAt(i);
if(ch==‘(‘)
{
stack.push(i);
}
else if(ch==‘)‘)
{
if(stack.isEmpty())
start = i;
else
{
stack.pop();
if(stack.isEmpty())
{
countMax = countMax>(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<len&&s.charAt(match)==‘)‘)
{
flag[i] = flag[i+1] + 2;
//处理((...))()的情况
if(match+1<len)
flag[i]+=flag[match+1];
}
result = result>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<len;i++)
{
if(s.charAt(i)==‘(‘)
{
depth++;
}
else
{
--depth;
if(depth<0)
{
start = i;
depth = 0;
}
else if(depth==0)
{
result = result>(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;
}