LeetCode 补充题 176. 括号配对与未匹配数量统计
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 20. 有效的括号
:::
给定仅含左右圆括号的字符串
s，允许跳过无法配对的括号，每对的左括号必须在右括号之前。返回
[成功配对数,未匹配左括号数,未匹配右括号数]。
示例 1：
输入：
s = ")(()"
输出：[1,1,1]
解释： 中间一个左括号能与末尾右括号配对，另有一个左括号和开头右括号未配对。
示例 2：
输入：
s = "(())"
输出：[2,0,0]
解释： 两个左括号分别与后面的右括号配对，无剩余括号。
提示：
- 字符串只含左右圆括号。
- 左括号必须先于与之配对的右括号。
- 返回顺序固定为
[配对数,剩余左括号数,剩余右括号数]。
题意分析
仅比较左右括号总数不够，因为左括号必须先出现。按原顺序扫描，保留尚未匹配的左括号数量，就能判断当前右括号是否还有合法配对对象。
解法：扫描未匹配左括号并即时配对
核心思路
[!blue]
left表示扫描前缀中尚未配对的左括号数，pairs是已完成配对数。遇到左括号先累加；遇到右括号且left > 0时立即消耗一个左括号，并增加一对。当前右括号若能配对而被跳过，不会让后续得到更多对：它消耗的一个左括号最多也只会匹配一个更晚的右括号。因此立即配对不会降低最优数量。
若此时
left == 0，当前右括号不可能与后面才出现的左括号配对，计入right后永久保留。扫描结束的left就是未匹配左括号数，按题面固定顺序返回三个统计值。
解题步骤
- 维护配对数、尚未匹配的左括号数和多余右括号数。
- 遇到左括号增加待匹配数；遇到右括号且存在左括号时完成一对。
- 没有可匹配左括号的右括号记为多余，最终按约定顺序返回三项。
代码实现
class Solution {
public int[] bracketCounts(String s) {
int pairs = 0;
int left = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
left++;
} else if (left > 0) {
left--;
pairs++;
} else {
right++;
}
}
return new int[] {
pairs,
left,
right
};
}
}
func bracketCounts(s string) []int {
pairs, left, right := 0, 0, 0
for _, c := range s {
if c == '(' {
left++
} else if left > 0 {
left--
pairs++
} else {
right++
}
}
return []int{
pairs,
left,
right,
}
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
已扫描部分的多余右括号无法被后面的左括号补救；扫描方向正好保证每对左括号在右括号之前。
易错点总结
[!yellow]
不能只用左右括号总数取最小值；")("虽然数量相等，但没有合法括号对。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 20. 有效的括号 | 简单 | 本题只有一种括号且允许跳过多余项，因此计数足够；多种括号的完整合法性判断需要保存类型。 |
| 32. 最长有效括号 | 困难 | 原题求连续有效区间，本题允许跳过错误括号，不能用配对总数乘二替代最长有效长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！