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-左括号起始位置，若不为空则减去peek的位置
1 package Longest.Valid.Parentheses; 2 3 import java.util.Stack; 4 5 public class LongestValidParentheses { 6 7 /** 8 * @param args 9 */ 10 public static void main(String[] args) { 11 // TODO Auto-generated method stub 12 LongestValidParentheses service=new LongestValidParentheses(); 13 //String s=")()())"; 14 String s="()(()"; 15 //String s="()"; 16 int a=service.longestValidParentheses(s); 17 System.out.println(a); 18 } 19 public int longestValidParentheses(String s) { 20 int len=s.length(); 21 Stack<Integer> stack=new Stack<Integer>(); 22 char[] charArray=s.toCharArray(); 23 int maxCount=0; 24 int firstleft=-1; 25 for(int i=0;i<len;i++){ 26 if(charArray[i]==‘(‘) 27 { 28 stack.push(i); 29 }else{ 30 if(!stack.isEmpty()){ 31 stack.pop(); 32 if(stack.isEmpty()){ 33 maxCount=Math.max(maxCount, i-firstleft); 34 }else{ 35 maxCount=Math.max(maxCount, i-stack.peek()); 36 } 37 }else{ 38 firstleft=i; 39 } 40 } 41 } 42 return maxCount; 43 } 44 }
Leetcode Longest Valid Parentheses
原文：http://www.cnblogs.com/criseRabbit/p/4267556.html