LeetCode 32. 最长有效括号
目录
题目描述
题意分析
给定只含
'('与')'的字符串，求其中最长的有效括号子串的长度。两个词决定了题目的全部难度。「有效」指每个左括号都能找到与之配对的右括号，等价的可逐字符检查的说法是：整段里左右括号数量相等，且任意前缀中右括号数量不超过左括号数量。「子串」指必须连续，这一点是本题与「统计能配成多少对」之类问题的分水岭——不连续的两段各自有效，拼起来也不算一个答案。因此答案不能靠数括号个数得到，必须知道有效片段的起止位置。
从这里可以读出两个信号。第一，答案一定是偶数，因为有效串左右括号成对。第二，字符串长度可达 $3 \times 10^4$，枚举所有 $O(n^2)$ 个子串再逐个验证的量级过不去，需要一个几乎线性的扫描过程，而扫描过程中必须能随时回答「以当前位置结尾的有效片段最远能往左延伸到哪」。
括号本身还有一条很强的结构性质：括号必须嵌套而不能交叉，所以一个右括号只可能与它左边最近的那个还没被配对的左括号配对，配对关系是唯一确定的，不存在选择。这条性质意味着「谁和谁配对」可以在一趟扫描里一次算清，不需要回头改。
需要留意的边界情形：空串答案为 0；全是左括号（如
"((("）或全是右括号（如")))"）答案都为 0；一个无法配对的右括号会把它左右两侧彻底隔断，例如"())()()"中下标 2 的右括号配不上，它左边只有长度 2 的有效段、右边有长度 4 的有效段，两段不能相加，答案是 4；而一个无法配对的左括号不会隔断，例如"(()"里下标 0 的左括号多余，但下标 1、2 仍构成长度 2 的有效串。左右两种「多余括号」的作用不对称，是本题最容易想漏的地方。
解法：栈维护未匹配下标
核心思路
栈保存未匹配左括号的下标，栈底保存最近一个未匹配右括号的下标。先放入哨兵
-1；每次成功匹配后，当前位置与栈顶之差就是以当前位置结尾的最长有效长度。
解题步骤
- 将
-1入栈，表示字符串起点之前的边界。- 遇到
'('时将其下标入栈。- 遇到
')'时弹栈；若栈空，将当前下标作为新的边界入栈。- 弹栈后若栈非空，用
i - stack.peek()更新最大长度。
代码实现
class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int result = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
continue;
}
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
result = Math.max(result, i - stack.peek());
}
}
return result;
}
}
func longestValidParentheses(s string) int {
stack := []int{-1}
result := 0
for i := range s {
if s[i] == '(' {
stack = append(stack, i)
continue
}
stack = stack[:len(stack)-1]
if len(stack) == 0 {
stack = append(stack, i)
} else if length := i - stack[len(stack)-1]; length > result {
result = length
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$，每个下标最多入栈、出栈各一次。
- 空间复杂度：$O(n)$，最坏情况下栈保存所有左括号下标。
关键点总结
- 栈存下标而不是字符，才能通过边界相减得到长度。
- 哨兵
-1统一处理从下标0开始的有效子串。- 未匹配的右括号是新的分段边界，必须将其下标压栈。
易错点总结
- 弹栈后为空却不压入当前下标，后续可能对空栈操作且长度会跨过无效字符。
- 长度应为
i - stack.peek()，不能加1。- 哨兵必须是
-1，使用0会漏算首字符。- 统计匹配对数无法保证括号连续，不能代替边界计算。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 只判定整串是否合法而不度量长度，但有三种括号类型，栈里必须存字符以校验配对类型 |
| 678. 有效的括号字符串 | 中等 | 多出可当左括号、右括号或空的 '*'，配对不再唯一，需要用左括号数量的可行区间代替单一计数 |
| 1249. 移除无效的括号 | 中等 | 求要删掉哪些位置而不是最长长度，栈里剩下的未配对下标正是删除集合，还要处理字母等其他字符 |
| 1614. 括号的最大嵌套深度 | 简单 | 输入保证合法，问的是嵌套层数而不是长度，一个记录当前深度的计数器就够，连栈都不必用 |