LeetCode 1249. 移除无效的括号

约 5 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 华为 微软 滴滴
标签
字符串 栈

题目描述

✅ 1249. 移除无效的括号

image-20260929000821173

image-20260929000821174

题意分析

从字符串中删除尽量少的左、右括号，使剩余括号有效，小写字母及所有保留字符的相对顺序不变。忽略字母后，有效括号要求每个前缀的左括号数不少于右括号数，且最终两者相等；最优结果可能不唯一，返回任意一个即可。

解法：栈标记无效括号位置

核心思路

[!blue]

从左到右扫描，用栈保存已经遇到、尚未匹配的左括号下标。遇到左括号就入栈；遇到右括号时，若栈不空，就与栈顶左括号配对并弹栈，若栈为空，就在 remove 中标记当前右括号。

栈为空时，当前已保留的前缀缺少一个左括号。后面的左括号不能反过来匹配此前的右括号，所以至少要从这个前缀删掉一个右括号；删除当前右括号就能恢复前缀合法性。遇到能配对的括号则尽量保留，使需要删除的右括号数量最少。

扫描结束后，栈中剩下的左括号都没有右括号与之配对，将它们也标记删除。最终左右括号总数必须相等；既然右括号已经按最少数量删除，剩余多出的左括号也至少要删除栈中这么多。算法恰好删除这两部分，因此总删除次数最少。具体删除位置可以替换，并不要求每个被标记的位置在所有最优答案中都被删除。

最后重新扫描，跳过标记位置并按原序保留其余字符。留下的每个右括号都有此前的左括号配对，也没有未闭合的左括号，结果一定有效；字母从未被标记，因而全部保留。

解题步骤

  1. 创建下标栈和全为 false 的删除标记数组。
  2. 从左到右扫描：左括号入栈；右括号能配对就弹栈，否则标记删除；字母直接跳过。
  3. 将扫描后仍留在栈中的左括号下标标记删除。
  4. 按原顺序收集所有未标记的字符并返回。

代码实现

class Solution {
    public String minRemoveToMakeValid(String s) {
        boolean[] remove = new boolean[s.length()];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);

            if (current == '(') {
                stack.push(i);
            } else if (current == ')') {
                // 没有可配左括号时标记当前右括号，形成一种最少删除方案
                if (stack.isEmpty()) {
                    remove[i] = true;
                } else {
                    stack.pop();
                }
            }
        }

        // 扫描后仍未配对的左括号按当前匹配方案删除
        while (!stack.isEmpty()) {
            remove[stack.pop()] = true;
        }

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            if (!remove[i]) {
                answer.append(s.charAt(i));
            }
        }

        return answer.toString();
    }
}

func minRemoveToMakeValid(s string) string {
    remove := make([]bool, len(s))
    stack := make([]int, 0)

    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else if s[i] == ')' {
            // 没有可配左括号时标记当前右括号，形成一种最少删除方案
            if len(stack) == 0 {
                remove[i] = true
            } else {
                stack = stack[:len(stack)-1]
            }
        }
    }

    // 扫描后仍未配对的左括号按当前匹配方案删除
    for _, index := range stack {
        remove[index] = true
    }

    answer := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        if !remove[i] {
            answer = append(answer, s[i])
        }
    }
    return string(answer)
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为字符串长度，每个括号最多入栈、出栈各一次，每个位置只处理常数次。
  • 空间复杂度：$O(n)$，下标栈、标记及结果。

关键点总结

[!green]

  • 先消除前缀中多余的右括号，再消除最终剩余的左括号，同时满足有效括号的两个条件。
  • 栈保存下标而不是括号字符，才能准确标记位置并保留字母及原有顺序。
  • 没有括号时原样返回；若全部字符都是无法配对的括号，返回空串，空串也是合法结果。

易错点总结

[!yellow]

  • 只删除多余右括号，留下未闭合的左括号。
  • 栈空仍弹出，既越界也没有删除该右括号。
  • 构造结果时只保留字母，会丢掉合法匹配括号。

相似题目

题目 难度 关联与区别
301. 删除无效的括号 困难 原题要返回全部最少删除结果，本题只需任意一个，可省去枚举与去重。
20. 有效的括号 简单 括号匹配是判定基础，本题允许删除无效圆括号并保留其他字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/25930455
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！