最长有效小括弧(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.

思路一：

使用栈的方式。

时间复杂度 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;
	}

最长有效小括弧(Longest Valid Parentheses)

原文：http://blog.csdn.net/cow__sky/article/details/18354269