[32. 最长有效括号]

难度 困难

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses

解法一：暴力枚举

从长到短枚举每一个子串，判断该子串是否为有效括号子串，如果是则返回该子串长度

class Solution { public int longestValidParentheses(String s) { int len = s.length(); //从长到枚举每一个子串 for(int size = len; size > 0; size--) { //子串长度为奇数时跳过 if(size % 2 == 0) { //长度为 size 的子串范围 int begin = 0, end = begin + size - 1; while(end < len) { if(valid(s.substring(begin, end + 1))) { return size; } begin++; end++; } } } return 0; } //判断该字符串是否为有效括号 public boolean valid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { if(s.charAt(i) == '(') { stack.push('('); } else if(!stack.isEmpty() && stack.peek() == '('){ stack.pop(); }else { return false; } } if(!stack.isEmpty()) { return false; } return true; } }

复杂度分析

时间复杂度： O(n³)。枚举全部子串 O(n²)，判断每个子串是否是有效括号 O(n)空间复杂度： O(n)。 子串的栈大小。

解法二：栈

用栈模拟一遍，将所有无法匹配的括号的位置全部置 1，然后寻找最长的连续的 0 的长度

class Solution { public int longestValidParentheses(String s) { int len = s.length(); int ans = 0; Stack<Integer> stack = new Stack<Integer>(); int[] mark = new int[len]; for(int i = 0; i < len; i++) { char c = s.charAt(i); //如果是左括号 '(' 则进栈 if(c == '(') { stack.push(i); }else { if(stack.isEmpty()) { //如果栈内没有相匹配的左括号 '(' , 则标记当前位置无法匹配 mark[i] = 1; }else { stack.pop(); } } } //将未匹配的左括号的位置标记为无法匹配 while(!stack.isEmpty()) { mark[stack.peek()] = 1; stack.pop(); } int count = 0; //寻找标记与标记之间的最大长度 for(int i = 0; i < len; i++) { if(mark[i] == 1) { count = 0; continue; } count++; ans = Math.max(ans, count); } return ans; } }

对于遇到的每个 ‘(’ ，我们将它的下标放入栈中

对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：

如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」

如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

class Solution { public int longestValidParentheses(String s) { int ans = 0; Stack<Integer> stack = new Stack<>(); //最开始将栈底元素设置为 -1， 即后一个没有被匹配的右括号的下标 stack.push(-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 { ans = Math.max(ans, i - stack.peek()); } } } return ans; } }

复杂度分析

时间复杂度： O(n)。空间复杂度： O(n)。栈的大小在最坏情况下会达到 n ，因此空间复杂度为 O(n) 。

解法三：动态规划

思路：

s[i] = ‘)’ 且 s[i − 1]= ‘(’，也就是字符串形如 “……()”，我们可以推出： dp[i] = dp[i − 2] + 2 是因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2 。

i-2 i-1 i . . . . . ( )

s[i] = ‘)’ 且 s[i − 1]=‘)’，也就是字符串形如 “……))”，我们可以推出： 如果 s[i − dp[i − 1] − 1] = ‘(’，那么 dp[i] = dp[i − 1] + dp[i−dp[i − 1] − 2] + 2

dp[i − 1] − 1 i-1 i ) ( ... . . ) ) ↑ ↑ ↑ dp[i-1] dp[i] class Solution { public int longestValidParentheses(String s) { int ans = 0; int dp[] = new int[s.length()]; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == ')') { //字符串形如 “……()” if (s.charAt(i - 1) == '(') { if(i >= 2) { dp[i] = dp[i - 2] + 2; }else { dp[i] = 2; } } //字符串形如 “……))” else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { if((i - dp[i - 1]) >= 2) { dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2; }else { dp[i] = dp[i - 1] + 2; } } ans = Math.max(ans, dp[i]); } } return ans; } }

复杂度分析

时间复杂度： O(n)。 n 为字符串的长度。空间复杂度： O(n)。数组 dp 的大小为 n。