问题背景
括号消除游戏是一款经典的益智消除类游戏：给定一串由左右括号组成的字符串，玩家需要找出其中最长的、可以有效消除的括号子串。有效的括号子串要求每个左括号都能找到对应的右括号进行匹配，且匹配顺序正确。
这一问题在编译原理中被称为”括号匹配”，是表达式解析、语法分析和代码格式化工具的核心基础。本文将用Java实现最长有效括号子串的查找算法，深入讲解单调栈与动态规划两种经典解法。
问题描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长有效（匹配且正确嵌套）括号子串的长度。
示例
- 输入：
"(()"，输出：2，最长有效子串为"()" - 输入：
")()())"，输出：4，最长有效子串为"()()" - 输入：
""，输出：0 - 输入：
"()(())"，输出：6，整个字符串都有效
解法一：单调栈
核心思路
栈天然适合处理配对问题。但直接匹配弹栈只能判断是否有效，无法追踪最长长度。关键技巧在于：栈中保存的不是括号本身，而是括号在字符串中的索引位置。
具体策略：
1. 初始化栈，压入哨兵值 -1（表示”上一个未匹配位置的左边界”）
2. 遇到 '('，将其索引入栈
3. 遇到 ')'，弹出栈顶元素：
– 如果栈为空，说明没有匹配的 '('，将当前 ')' 的索引入栈作为新的哨兵
– 如果栈不为空，当前有效子串长度为 当前索引 - 栈顶索引
为什么需要哨兵？
当遇到 ')' 成功匹配时，栈顶保存的是上一个未匹配位置的索引。用这个索引作为左边界，可以快速计算出当前连续有效子串的长度。
解法二：动态规划
核心思路
定义 dp[i] 为以第 i 个字符结尾的最长有效括号子串的长度。
状态转移：
– 若 s[i] == '('，dp[i] = 0（以左括号结尾不可能是有效子串的结尾）
– 若 s[i] == ')'：
– 若 s[i-1] == '('，则 dp[i] = dp[i-2] + 2（直接配对）
– 若 s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('，则 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（跨越配对）
Java完整实现
import java.util.Stack;
import java.util.Arrays;
/**
* 最长有效括号子串 - 单调栈与动态规划双重解法
* 对应力扣第32题
*/
public class LongestValidParentheses {
/**
* 解法一：单调栈
* 栈中保存索引，哨兵技巧追踪左边界
* 时间复杂度：O(n) 空间复杂度：O(n)
*/
public int longestValidParenthesesStack(String s) {
if (s == null || s.length() < 2) {
return 0;
}
Stack<Integer> stack = new Stack<>();
// 哨兵：表示上一个未匹配位置的左边界
stack.push(-1);
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
// 左括号索引入栈，等待匹配
stack.push(i);
} else {
// 右括号：尝试匹配
stack.pop(); // 弹出栈顶（期望是匹配的左括号或哨兵）
if (stack.isEmpty()) {
// 没有匹配的左括号，当前右括号作为新的哨兵
stack.push(i);
} else {
// 匹配成功，计算当前有效子串长度
int currentLen = i - stack.peek();
maxLen = Math.max(maxLen, currentLen);
}
}
}
return maxLen;
}
/**
* 解法一优化：使用数组模拟栈，提升性能
*/
public int longestValidParenthesesArrayStack(String s) {
if (s == null || s.length() < 2) {
return 0;
}
int n = s.length();
int[] stack = new int[n + 1]; // 数组模拟栈
int top = 0; // 栈顶指针，stack[0]作为哨兵
stack[top] = -1;
int maxLen = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
stack[++top] = i;
} else {
top--; // 弹出栈顶
if (top < 0) {
// 栈空，当前右括号作为新哨兵
stack[++top] = i;
} else {
maxLen = Math.max(maxLen, i - stack[top]);
}
}
}
return maxLen;
}
/**
* 解法二：动态规划
* dp[i]表示以s[i]结尾的最长有效括号子串长度
* 时间复杂度：O(n) 空间复杂度：O(n)
*/
public int longestValidParenthesesDP(String s) {
if (s == null || s.length() < 2) {
return 0;
}
int n = s.length();
int[] dp = new int[n];
int maxLen = 0;
for (int i = 1; i < n; i++) {
char c = s.charAt(i);
if (c == ')') {
if (s.charAt(i - 1) == '(') {
// 情形1：...() 直接配对
// dp[i] = 前面有效长度 + 2
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (s.charAt(i - 1) == ')') {
// 情形2：...)) 跨越配对
// 需要检查 i - dp[i-1] - 1 位置是否为 '('
int prevLen = dp[i - 1];
int matchPos = i - prevLen - 1;
if (matchPos >= 0 && s.charAt(matchPos) == '(') {
// 跨越匹配成功
dp[i] = prevLen + 2;
// 还要加上matchPos之前的有效长度
if (matchPos - 1 >= 0) {
dp[i] += dp[matchPos - 1];
}
}
}
maxLen = Math.max(maxLen, dp[i]);
}
// 以'('结尾，dp[i]保持0
}
return maxLen;
}
/**
* 解法三：双向遍历（最优空间复杂度）
* 利用有效子串中左右括号数量相等的性质
* 时间复杂度：O(n) 空间复杂度：O(1)
*/
public int longestValidParenthesesTwoPass(String s) {
if (s == null || s.length() < 2) {
return 0;
}
int left = 0, right = 0, maxLen = 0;
int n = s.length();
// 从左向右遍历
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') left++;
else right++;
if (left == right) {
// 左右括号数量相等，形成一个有效子串
maxLen = Math.max(maxLen, 2 * right);
} else if (right > left) {
// 右括号过多，不可能再形成有效子串，重置
left = right = 0;
}
}
left = right = 0;
// 从右向左遍历（处理左括号过多的情况）
for (int i = n - 1; i >= 0; i--) {
char c = s.charAt(i);
if (c == '(') left++;
else right++;
if (left == right) {
maxLen = Math.max(maxLen, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxLen;
}
/**
* 扩展：返回最长有效子串的具体内容（而非仅长度）
*/
public String getLongestValidSubstring(String s) {
if (s == null || s.length() < 2) {
return "";
}
int n = s.length();
int[] dp = new int[n];
int maxLen = 0;
int endIndex = -1;
for (int i = 1; i < n; i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else {
int prevLen = dp[i - 1];
int matchPos = i - prevLen - 1;
if (matchPos >= 0 && s.charAt(matchPos) == '(') {
dp[i] = prevLen + 2;
if (matchPos - 1 >= 0) {
dp[i] += dp[matchPos - 1];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
endIndex = i;
}
}
}
if (maxLen == 0) return "";
return s.substring(endIndex - maxLen + 1, endIndex + 1);
}
/**
* 扩展：括号匹配检查器（判断整个字符串是否有效）
*/
public boolean isValidParentheses(String s) {
if (s == null || s.length() == 0) return true;
int balance = 0;
for (char c : s.toCharArray()) {
if (c == '(') balance++;
else if (c == ')') balance--;
if (balance < 0) return false; // 右括号过多
}
return balance == 0;
}
// ============ 测试入口 ============
public static void main(String[] args) {
LongestValidParentheses solution = new LongestValidParentheses();
String[] testCases = {
"(()",
")()())",
"",
"()(())",
"())(()())",
"((()))",
"()(()"
};
System.out.println("===== 最长有效括号测试 =====");
for (String test : testCases) {
System.out.println("\n输入: \"" + test + "\"");
System.out.println("栈解法长度: " + solution.longestValidParenthesesStack(test));
System.out.println("数组栈长度: " + solution.longestValidParenthesesArrayStack(test));
System.out.println("DP解法长度: " + solution.longestValidParenthesesDP(test));
System.out.println("双向遍历长度: " + solution.longestValidParenthesesTwoPass(test));
System.out.println("最长子串内容: \"" + solution.getLongestValidSubstring(test) + "\"");
System.out.println("是否全部有效: " + solution.isValidParentheses(test));
}
}
}
复杂度对比
| 解法 | 时间复杂度 | 空间复杂度 | 核心思想 | 适用场景 |
|---|---|---|---|---|
| 单调栈 | O(n) | O(n) | 哨兵追踪左边界 | 需要获取子串位置 |
| 数组模拟栈 | O(n) | O(n) | 避免Stack对象开销 | 性能敏感场景 |
| 动态规划 | O(n) | O(n) | 状态记录以i结尾的最长长度 | 需要获取子串内容 |
| 双向遍历 | O(n) | O(1) | 利用括号数量平衡性质 | 空间受限场景 |
关键技巧详解
哨兵技巧
在栈解法中，-1作为初始哨兵至关重要。当遇到 ')' 成功匹配时，i - stack.peek() 计算的是从上一个未匹配位置之后到当前位置的距离，这正是有效子串的长度。
DP跨越配对
动态规划中最难理解的是 ...)) 情形。此时 dp[i-1] 告诉我们以 i-1 结尾的最长子串长度，跳过这段长度后检查前一个位置是否为 '('，如果是，则实现跨越匹配。
双向遍历的数学原理
有效子串必然左右括号数量相等。从左向右遍历时，当 right > left 说明已不可能有效；但 left > right 时仍可能有效（后面有更多右括号）。因此需要反向遍历处理这种情况。
扩展应用
- 多类型括号匹配：扩展栈结构，处理
[]、{}等多种括号 - 最少添加括号数：计算使字符串有效所需的最少括号数
- 括号生成：生成所有n对有效括号组合（回溯法）
- 表达式求值：基于有效括号的嵌套关系解析数学表达式
