最长有效括号

大家好，欢迎来到IT知识分享网。

难度：困难

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串

的长度。

示例 1：

输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()" 

示例 2：

输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" 

示例 3：

输入：s = "" 输出：0 

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

最长有效括号是动态规划类型题目的一种经典题目，当然要解决这个问题我们也可以使用栈（Stack）这种数据结构来追踪括号的有效性，也可以用动态规划（Dynamic Programming）方法来解决。

方法 1：使用栈

我们使用一个栈来存储当前未匹配的括号的位置。每当我们遇到一个有效的匹配时，我们可以计算当前有效括号字符串的长度。

import java.util.Stack; public class LongestValidParentheses { public int longestValidParentheses(String s) { Stack<Integer> stack = new Stack<>(); // 先放入-1，用于计算长度 stack.push(-1); int maxLength = 0; for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); // 当遇到左括号，压入栈 if (ch == '(') { stack.push(i); } else { // 遇到右括号，弹出栈顶元素 stack.pop(); if (stack.isEmpty()) { // 如果栈空，说明当前没有有效括号，压入当前下标 stack.push(i); } else { // 更新最长有效长度 maxLength = Math.max(maxLength, i - stack.peek()); } } } return maxLength; } public static void main(String[] args) { LongestValidParentheses lvp = new LongestValidParentheses(); System.out.println(lvp.longestValidParentheses("(()")); // 输出 2 System.out.println(lvp.longestValidParentheses(")()())")); // 输出 4 System.out.println(lvp.longestValidParentheses("")); // 输出 0 } } 

代码解析：

1. 定义栈：我们创建一个 Stack<Integer> 来存储括号的索引。
2. 初始栈状态：我们首先向栈中放入 -1，这个值用来计算有效括号子串的长度。如果当前没有有效括号，那么 top 元素是 -1，方便之后计算长度。
3. 遍历字符串：遍历整个字符串 s，并获取每个字符。
4. 处理左括号：如果字符是左括号 '('，我们将其索引 i 压入栈。
5. 处理右括号：当我们遇到右括号 ')'：
   • 我们先弹出栈顶元素，如果栈为空（说明当前没有匹配的左括号），则我们将当前右括号的索引 i 压入栈。
   • 如果栈不为空，说明当前的右括号能够匹配栈中的左括号。我们计算有效括号的长度：当前索引 i 和栈顶元素的索引之间的距离，更新 maxLength。
6. 返回结果：最终返回 maxLength，代表最长有效括号子串的长度。

方法 2：动态规划

我们可以使用动态规划来跟踪以每个字符结尾的有效括号长度。

public class LongestValidParentheses { public int longestValidParentheses(String s) { int maxLength = 0; int n = s.length(); int[] dp = new int[n]; // dp[i]: 以i结尾的有效括号的长度 for (int i = 1; i < n; i++) { if (s.charAt(i) == ')') { // 当s[i-1]是'('时，形成一个有效括号对 if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } // 当s[i-1]是')'时，寻找之前匹配的'(' else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2; } maxLength = Math.max(maxLength, dp[i]); } } return maxLength; } public static void main(String[] args) { LongestValidParentheses lvp = new LongestValidParentheses(); System.out.println(lvp.longestValidParentheses("(()")); // 输出 2 System.out.println(lvp.longestValidParentheses(")()())")); // 输出 4 System.out.println(lvp.longestValidParentheses("")); // 输出 0 } } 

代码解析：

1. 定义动态规划数组：dp[i] 表示以索引 i 结尾的有效括号子串的长度。
2. 初始化：maxLength 用来跟踪最长有效括号的长度。
3. 遍历字符串：从索引 1 开始遍历字符串，检查当前字符是否为 ')'。
4. 处理有效括号对：如果前一个字符是 '('（即 s[i-1]），那么 dp[i] 应该等于前一个有效子串长度（dp[i - 2]，如果 i-2 有效的话，减去 2 表示去掉这对括号）加上 2。
5. 处理嵌套/连续有效括号：如果当前字符为 ')' 且前一个字符为 ')'，说明我们需要回退到最近的有效括号：
   • 检查在 dp[i - 1] 之前的字符是否为 '('。
   • 如果是，dp[i] 的值会是 dp[i - 1]，加上可能存在的前面有效的括号长度 dp[i - dp[i - 1] - 2]，再加上 2（这对括号本身的长度）
6. 更新最大长度：在每次计算 dp[i] 后，都更新 maxLength。
7. 进行测试：在 main 方法中实例化 LongestValidParentheses 类并测试几个示例字符串，输出最长有效括号的长度。

总结

• 栈方法：使用栈来追踪未匹配的 ( 的位置，处理括号时弹出栈顶元素，计算有效子串长度，适合处理的问题，时间复杂度为 O(n)，空间复杂度为 O(n)。
• 动态规划方法：使用数组记录以每个字符结尾的有效括号长度，进行更新和计算，时间复杂度为 O(n)，空间复杂度也为 O(n)（可以进一步优化到 O(1)）。