Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is"()()"
超过17.81%，不是用的栈。
基本思路是：
从左至右遍历字符串，找出所有这样的子串[begin,end]，其任意的子串的左括号数量>有括号数量。将这样的区间放入一个区间链表left中。
然后从右至左遍历字符串，找出所有这样的字符串[begin,end]，其任意的子串的右括号数量>左括号的数量。 将这样的区间放入一个区间链表right中。
取两个区间集合left，right的交集。最大的子区间的元素数量就是最终结果。
1 class Solution { 2 class Perfect { 3 int start; 4 int end; 5 6 public Perfect(int start, int end) { 7 this.start = start; 8 this.end = end; 9 } 10 11 @Override 12 public String toString() { 13 return "[" + start + 14 "," + end + 15 ‘]‘; 16 } 17 } 18 19 public int longestValidParentheses(String s) { 20 int LL = 0, LR = 0, RL = 0, RR = 0; 21 List<Perfect> left = new ArrayList<>(); 22 List<Perfect> right = new ArrayList<>(); 23 int RLborder=s.length()-1,LRborder=0; 24 for (int i = 0; i < s.length(); i++) { 25 //L-->R 26 if (s.charAt(i) == ‘(‘) 27 ++LL; 28 else 29 ++LR; 30 if (LR > LL) { 31 int start = i - (LL + LR) + 1;//有问题 32 int end = i - 1; 33 if (start >= 0 && end >= 0 && start < end) 34 left.add(new Perfect(start, end)); 35 LR = LL = 0; 36 LRborder=i+1; 37 } 38 if (i == s.length() - 1 && LR == LL && LR != 0) { 39 left.add(new Perfect(s.length() - LR - LL, s.length() - 1)); 40 } 41 42 43 //R-->L 44 if (s.charAt(s.length() - 1 - i) == ‘(‘) 45 ++RL; 46 else 47 ++RR; 48 if (RL > RR) { 49 int start = s.length() - i; 50 int end = s.length() - 1 - i + RL + RR - 1; 51 if (start >= 0 && end <= s.length() - 1 && start < end) 52 right.add(new Perfect(start, end)); 53 RL = RR = 0; 54 RLborder=s.length()-1-i-1; 55 } 56 if (s.length() - 1 - i == 0 && RL == RR && RL != 0) { 57 right.add(new Perfect(0, RL + RR - 1)); 58 } 59 } 60 if (LR < LL && s.length()-LRborder !=1) { 61 left.add(new Perfect(LRborder,s.length()-1)); 62 } 63 if (RL < RR && RLborder-0!=1) { 64 right.add(new Perfect(0, RLborder)); 65 } 66 67 68 for (int j = 0; j < left.size(); j++) { 69 System.out.println(left.get(j)); 70 } 71 System.out.println("*********"); 72 for (int j = right.size() - 1; j >= 0; --j) { 73 System.out.println(right.get(j)); 74 } 75 76 //取left和right的交集 77 int res = 0; 78 for (int i = 0; i < left.size(); i++) { 79 //left的i位置区间和right的j区间做交集 80 for (int j = right.size()-1; j >=0; j--) { 81 int maxStart = Math.max(left.get(i).start, right.get(j).start); 82 int minEnd = Math.min(left.get(i).end, right.get(j).end); 83 if (maxStart < minEnd) { 84 res = res < minEnd - maxStart +1 ? minEnd - maxStart+1 : res; 85 }else if (left.get(i).start > right.get(j).end){ 86 continue; 87 }else 88 break; 89 } 90 } 91 return res; 92 } 93 }
leetCode 32. Longest Valid Parentheses
原文：https://www.cnblogs.com/yfs123456/p/10990728.html