力扣-32.最长有效括号

题目描述

32.最长有效括号

解法一：动态规划

class Solution { public int longestValidParentheses(String s) { int res = 0; int[] dp = new int[s.length()]; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == \')\') { if (i >= 1 && s.charAt(i - 1) == \'(\') {  if (i >= 2) { //形如()() dp[i] = dp[i - 2] + 2;  } else { //形如() dp[i] = 2;  } } else if (i >= 1 && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == \'(\') {  if (i - dp[i - 1] - 2 >= 0) { //形如()((())) dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;  } else { //形如((())) dp[i] = dp[i - 1] + 2;  } } } res = Math.max(res, dp[i]); } return res; }}

小结：注意边界条件，以及两类不同情况()与))。

解法二：栈

class Solution { public int longestValidParentheses(String s) { Stack<Integer> stack = new Stack<>(); int res = 0; stack.push(-1);// 初始压入-1作为边界条件，便于计算长度  for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == \'(\') { stack.push(i); } else { stack.pop();// 先弹出匹配的元素，栈顶是未匹配的边界 if (stack.empty()) {// 如果栈为空，将当前索引作为新的边界压入栈中  stack.push(i); } else {  res = Math.max(res, i - stack.peek()); } } } return res; }}

小结：括号匹配用栈的思路比较容易想到，但栈中的元素是位置坐标而不是括号，利用下标差来计算长度。