力扣-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;}
}

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