首页 > 代码库 > Leetcode Longest Valid Parentheses
Leetcode 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.
对于这道题，用动态规划方法时间超时，后来看了别人的解法
建立一个栈，用来保存（的位置信息，同时用一个符号表示第一个（的位置信息，如果遇到（就压站，如果遇到）且栈不为空的时候就弹出，并判断弹出后是否为空，若为空则最大长度为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 stub12 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。