题目描述：
题解：
public class LongestValidParentheses { /** * 解法一：暴力解法，超时了 * 从最大长度的字串，判断字串是否是合格的，如果是，那么当前字串长度就是结果 * @param s * @return */ public int longestValidParentheses2(String s) { int len = s.length(); Stack<Character> stack = new Stack<>(); String subStr; boolean flag = true; for (int k = len; k >= 1; k--) { for (int i = 0; i+k-1 < len; i++) { subStr = s.substring(i,i+k); stack.clear(); flag = true; for (int j = i; j < i+k; j++) { if (s.charAt(j) == '(') { stack.push(s.charAt(j)); } else { if (stack.isEmpty()) { flag = false; break; } else { stack.pop(); } } } if (flag && stack.isEmpty()) { return k; } } } return 0; } /** * 用栈模拟一遍，将所有无法匹配的括号的位置全部置0 * 例如: "()(()"的mark为[1, 1, 0, 1, 1] * 再例如: ")()((())"的mark为[0, 1, 1, 0, 1, 1, 1, 1] * 经过这样的处理后, 此题就变成了寻找最长的连续的1的长度 * @param s * @return */ public int longestValidParentheses3(String s) { if (s == null || s.isEmpty()) return 0; int len = s.length(); Stack<Integer> stack = new Stack<>(); int[] tag = new int[len]; for (int i = 0; i < len; i++) { if (s.charAt(i) == '(') { stack.push(i); } else { if (!stack.isEmpty()) { tag[stack.pop()] = 1; tag[i] = 1; } } } int pre = tag[0]; int result = 0, flag = 0; if (pre == 1) { flag++; } for (int i = 1; i < len; i++) { System.out.print(tag[i] + " "); if (pre == tag[i]) { if (pre == 1) { flag++; } } else { pre = tag[i]; if (pre == 0) { result = Math.max(result,flag); flag = 0; } else { flag++; } } } result = Math.max(result,flag); return result; } public int longestValidParentheses(String s) { if (s == null || s.isEmpty()) return 0; int len = s.length(); Stack<Character> stack = new Stack<>(); int tag = 0, result = 0, flag = 0; for (int i = 0; i < len; i++) { if (s.charAt(i) == '(') { stack.push(s.charAt(i)); if (tag > 0) { flag++; if (flag > 1) { result = Math.max(result,tag); tag = 0; } } else { flag = 0; } } else { if (!stack.isEmpty()) { stack.pop(); tag += 2; } } } if (tag > 0) { result = Math.max(result,tag); tag = 0; } return result; } }