LeetCode 1249. 移除无效的括号

Categories:

题目描述
思路分析
1. 解法一：两次遍历删除多余括号（推荐）
相似题目

题目描述

✅ 1249. 移除无效的括号

思路分析

解法一：两次遍历删除多余括号（推荐）

核心思路：

第一次遍历删除多余的右括号 )，保证任意前缀中 ) 不超过 (。

第二次从右向左删除多余的左括号 (。

其余字符保持原顺序。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于构建结果。

class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder();
        int balance = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                balance++;
                sb.append(c);
            } else if (c == ')') {
                if (balance > 0) {
                    balance--;
                    sb.append(c);
                }
            } else {
                sb.append(c);
            }
        }

        StringBuilder res = new StringBuilder();
        int removeLeft = balance;
        for (int i = sb.length() - 1; i >= 0; i--) {
            char c = sb.charAt(i);
            if (c == '(' && removeLeft > 0) {
                removeLeft--;
                continue;
            }
            res.append(c);
        }

        return res.reverse().toString();
    }
}

func minRemoveToMakeValid(s string) string {
	buf := make([]byte, 0, len(s))
	balance := 0

	for i := 0; i < len(s); i++ {
		c := s[i]
		if c == '(' {
			balance++
			buf = append(buf, c)
		} else if c == ')' {
			if balance > 0 {
				balance--
				buf = append(buf, c)
			}
		} else {
			buf = append(buf, c)
		}
	}

	res := make([]byte, 0, len(buf))
	removeLeft := balance
	for i := len(buf) - 1; i >= 0; i-- {
		c := buf[i]
		if c == '(' && removeLeft > 0 {
			removeLeft--
			continue
		}
		res = append(res, c)
	}

	// 反转结果
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}
	return string(res)
}

相似题目

题目	难度	考察点
1249. 移除无效的括号	中等	栈/双遍历
20. 有效的括号	简单	栈
301. 删除无效的括号	困难	BFS/回溯
921. 使括号有效的最少添加	中等	贪心
678. 有效的括号字符串	中等	贪心/栈
32. 最长有效括号	困难	栈/DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/25930455