首页 > 代码库 > 32. Longest Valid Parentheses
32. 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.
思路：hard题确实不好想，参考了discussion。其实思路和maxsubarray一样，用一个globalmax来存最大值。从左到右遍历，碰到左边符号数量等于右边符号数量，计算长度（用一个prev pointer记录之前的位置），更新globalmax。情况不符，也就是左边符号数量少于右边符号数量，将pointer向右移一位（这个很重要），并且reset count和max。这道题比较tricky的地方在于一遍从左到右不够，需要从右到左再扫一遍。因为例如（（）的情况，跳出循环但是max没有更新，其实max应该是2.所以要从右到左再扫一遍。
public class Solution { public int longestValidParentheses(String s) { if(s==null||s.length()==0) { return 0; } int count=0; int prev=0; int max=0; for(int i=0;i<s.length();i++) { if(s.charAt(i)==‘(‘) { count++; } else { count--; } if(count==0) { max=Math.max(i-prev+1,max); } if(count<0) { count=0; prev=i+1; } } int count2=0; int prev2=s.length()-1; for(int j=s.length()-1;j>=0;j--) { if(s.charAt(j)==‘)‘) { count2++; } else { count2--; } if(count2==0) { max=Math.max(prev2-j+1,max); } if(count2<0) { count2=0; prev2=j-1; } } return max; }}
32. Longest Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。