有效的括号字符串如何用贪心判断？（LeetCode 678）

简化版

把 * 当成「可以是左括号、右括号或空」后，不要枚举所有情况，而是维护当前可能的左括号数量区间 [low, high]。

扫描时 ( 让区间整体加 1，) 让区间整体减 1，* 让下界减 1、上界加 1；过程中 high < 0 说明右括号太多，最后 low == 0 才能配平。

详细版

这题的关键是把不确定的 * 看成「多种选择形成的可行区间」。low 表示在最乐观地把一些 * 当右括号或空后，仍然至少还剩多少个未匹配左括号；high 表示在最保守地把 * 都当左括号后，最多可能有多少个未匹配左括号。

遇到 (：low++，high++。遇到 )：low--，high--。遇到 *：它可以抵消一个左括号，也可以当左括号，所以 low--、high++。

每一步后要把 low 截断到 0，因为未匹配左括号数量不可能为负；但如果 high < 0，表示无论怎么把前面的 * 解释，都已经右括号过多，直接返回 false。扫描结束后，如果 low == 0，说明存在一种解释能完全配平。

boolean checkValidString(String s) {
    int low = 0, high = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            low++;
            high++;
        } else if (c == ')') {
            low--;
            high--;
        } else {
            low--;
            high++;
        }
        if (high < 0) return false;
        low = Math.max(low, 0);
    }
    return low == 0;
}

完整版教学

一、为什么不能直接贪心地给每个星号定身份

* 有三种身份：(、)、空。直觉上可以遇到缺什么就补什么，但这个选择会影响后面的字符，局部看起来对，后面可能出问题。比如 (*)) 中，星号最好当 (；而 (*) 中，星号最好当空；在 (*() 里，星号又可能需要当 )。如果每个星号立刻定死身份，就会过早承诺，失去后续调整空间。

这类题的贪心不是「马上做一个具体选择」，而是「保留所有可能选择的边界」。我们不关心具体哪一个 * 变成什么，只关心扫描到当前位置时，未匹配左括号数量可能落在哪个范围。只要这个范围还和合法状态有交集，就说明仍有机会配平。

二、把状态压成一个区间

设扫描到某个位置后，未匹配左括号数量可能有很多值。例如 (* 后，可能值是 {0, 1, 2}：星号当 ) 得 0，当空得 1，当 ( 得 2。这个集合在本题中始终可以用连续区间表示，所以只维护最小值 low 和最大值 high。

low  = 当前至少可能剩多少个未匹配 '('
high = 当前至多可能剩多少个未匹配 '('
合法要求：最终 0 落在可能范围里

区间表示的好处是不用保存所有组合。长度为 n 的字符串如果暴力枚举星号，最坏有 3^k 种解释；而区间贪心每个字符只更新两个整数，时间 O(n)，空间 O(1)。

三、三个字符如何更新区间

遇到 (，所有可能状态都多一个未匹配左括号，所以 [low, high] 变成 [low+1, high+1]。遇到 )，所有可能状态都要消耗一个左括号，所以变成 [low-1, high-1]。遇到 * 时，最小值可以把它当 ) 来尽量消耗左括号，最大值可以把它当 ( 来增加左括号，所以变成 [low-1, high+1]。

字符	low 变化	high 变化	含义
`(`	`+1`	`+1`	必然增加一个待匹配左括号
`)`	`-1`	`-1`	必然消耗一个左括号
`*`	`-1`	`+1`	可当右括号、空或左括号

记忆钩子：low 代表「最乐观还剩多少左括号」，high 代表「最保守最多剩多少左括号」；只要右边界没塌，未来就还有补救空间。

四、为什么 low 要截断到 0

未匹配左括号数量不可能小于 0。如果根据转移得到 low = -1，它不是说真的有负数个左括号，而是说存在某种解释已经把前缀完全配平，甚至还能把某个 * 改成空来避免多消耗。因此下界应该截断为 0。

用 s = "*" 举例。初始 [0,0]，遇到 * 后理论更新为 [-1,1]，真实可行的未匹配左括号数量是 {0,1}：星号当空得到 0，当左括号得到 1。这里 -1 只是数学更新的中间结果，要修正成 0。

五、为什么 high 小于 0 可以立刻失败

high 是最多可能剩的左括号数量。如果 high < 0，说明即使把之前能当左括号的 * 都尽量当左括号，也挡不住当前右括号数量过多。此时前缀已经不可能合法，后面再出现左括号也无法修复「前缀右括号多」的问题。

例如 ")*(" 的第一个字符就是 )。初始 [0,0]，遇到 ) 后变成 [-1,-1]，high < 0，说明没有任何左括号可被它匹配。括号合法性要求任意前缀中右括号不能超过可用左括号，这个前缀条件已经被破坏。

六、用数字例子完整走一遍

以 s = "(*))" 为例，过程如下：

初始      [0,0]
读 '('   [1,1]
读 '*'   [0,2]
读 ')'   [0,1]   // 先得到 [-1,1]，low 截断为 0
读 ')'   [0,0]
最终 low=0，存在合法解释：星号当 '('

再看 s = "(*()"：

初始      [0,0]
读 '('   [1,1]
读 '*'   [0,2]
读 '('   [1,3]
读 ')'   [0,2]
最终 low=0，所以也合法：星号当空，得到 "()()"

这个例子能看出，算法并没有固定某个星号的身份，而是只判断「是否存在一种身份分配」。

七、常见误区与追问

误区：遇到 * 直接优先当右括号。 这样会过早消耗左括号，后面可能需要它当左括号时已经来不及。
误区：只维护一个 balance。 一个数字只能表示确定状态，无法表达 * 带来的多种可能。
误区：low 变负就返回 false。 low 负数只说明乐观情况下已经配平，应截断到 0，不代表失败。
追问：为什么最终看 low == 0？ 因为 low 是最少未匹配左括号，如果最少都大于 0，说明无论怎么解释都有左括号剩余。
追问：复杂度是多少？ 每个字符处理一次，时间 O(n)，只用两个整数，空间 O(1)。
追问：能用栈做吗？ 可以用两个栈记录左括号和星号下标，但区间贪心更简洁，空间也更低。

八、加强记忆

这题要记住「不确定选择不要急着定死，先维护可行范围」。low 是最乐观的左括号余额，high 是最保守的左括号余额；( 让二者都加一，) 让二者都减一，* 让范围向两边扩张。过程中 high < 0 表示前缀右括号已经压垮所有可能，最终 low == 0 表示存在一种解释能把左括号全部消掉。抓住「星号产生区间，区间保留可能性」这个锚点，就能把这题和普通括号 balance 区分开。

简化版

详细版