leetcode 32: 最长有效括号（栈方法 和 双指针追逐法）

最长有效括号匹配

题解

括号匹配充要条件（规律）

规律1:在一段长度以内，左右括号数量是相同的规律2:直到最后一个字符为止，每一个前缀的左括号数量都大于右括号的数量

题解框架

将字符串分割为一系列字串，确保每一段都不会破坏规则

题解思路

根据规律2，确保当前子串的前缀是左括号更多。我们可以一个个字符串向后遍历，使用一个计数器cnt统计左右括号的差值，当遇到左边括号计数器就+1，右边就-1，cnt<0的时候说明当前子串再向右就一定不合法了，因为至少有一个前缀是不符合规律2的。通过规律2，子串可以划分成若干段，并且段与段之间是不能跨越的（注意，最后一个字符一定是右括号，除非没有右括号）再将这些段结合规律1来进行匹配规律1对应的是括号匹配题目的常见算法，我们可以利用一个栈，遇到做括号，就装入做括号，遇到右括号，就将栈顶的做括号抛弃，再次注意，这个匹配机制是针对每一段而言的

实现：栈

class Solution { public int longestValidParentheses(String s) { int res = 0, n = s.length(); Stack<Integer> stack = new Stack<>(); int start = -1; for(int i = 0;i < n;i++){ if(s.charAt(i)=='('){ stack.push(i); }else{ if(!stack.isEmpty()){ stack.pop(); int tmp = 0; if(!stack.isEmpty()) tmp = i - stack.peek(); else //整段都满足情况 tmp = i - start; res = res > tmp?res:tmp; } else{ start = i; } } } return res; } }

实现：左右扫描法（更快，且逻辑更好记，leetcode题解）

细节：左右括号指针相互追逐，相遇的时候计算一下长度。 public class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, maxlength = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * right); } else if (right > left) { left = right = 0; } } left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, 2 * left); } else if (left > right) { left = right = 0; } } return maxlength; } } 题目 最长有效括号