在 LeetCode 上有一道经典题：有效的括号字符串（Valid Parenthesis String）。给定一个只包含 (、) 和 * 的字符串，其中 * 可以视为 (、) 或空字符，判断该字符串是否能变成一个合法的括号序列。

这道题的标准解法是双栈法，听起来有点抽象。但如果我们把它想象成一档大型相亲综艺节目，一切就豁然开朗了。

---

节目设定

• 男嘉宾​ → 代表 (（左括号）
• 女嘉宾​ → 代表 )（右括号）
• AI 机器人​ → 代表 *（星号），它可以扮演男嘉宾、女嘉宾，也可以选择不登场（空字符）
• 牵手成功​ → 括号匹配成功
• 节目流程：导演（遍历程序）按出场顺序依次邀请嘉宾上台，并实时记录尚未配对的男嘉宾和AI机器人。

---

第一幕：女嘉宾登场（遇到 )）

当一位女嘉宾走上舞台，她需要立刻牵手一位男嘉宾。导演的规则是：

1. 优先让在场的男嘉宾牵手（如果还有未配对的 (）。
2. 如果没有男嘉宾，就让AI机器人临时扮演男嘉宾（用 * 充当 (）。
3. 如果男嘉宾和AI机器人都不在场，说明这位女嘉宾无人可牵，节目失败（返回 False）。

为什么优先用男嘉宾？​

因为男嘉宾是确定的，AI机器人可以灵活变换角色。先消耗确定性资源，保留灵活性，这是算法中的“贪心”智慧。

---

第二幕：男嘉宾登场（遇到 (）

男嘉宾走上台后，暂时没有女嘉宾可牵，所以他会被导演记录在“等待区”（左栈）。他只能等待后面的女嘉宾或AI机器人来配对。

---

第三幕：AI机器人登场（遇到 *）

AI机器人走上台时，导演不会立刻决定它的角色，而是把它也记录在“机器人等待区”（星栈）。它的作用将在后面揭晓——可能扮演男嘉宾去牵女嘉宾，也可能扮演女嘉宾去牵男嘉宾，或者干脆不参与。

这就是算法的核心：延迟决策。不急着决定星号是什么，而是先存着，等需要时再灵活使用。

---

第四幕：节目结束，处理剩下的嘉宾

当所有嘉宾都走过场后，等待区可能还剩下一些男嘉宾和AI机器人。这时导演需要让AI机器人扮演女嘉宾，去牵手剩下的男嘉宾。但有一个关键条件：

AI机器人必须站在男嘉宾的右边（即AI机器人的出场顺序索引大于男嘉宾的索引），因为女嘉宾只能在男嘉宾之后登场，否则顺序颠倒，节目无法播出（括号不合法）。

导演的做法是：

• 每次从男嘉宾等待区取出最后一位男嘉宾（最晚登场的），再从机器人等待区取出最后一位AI机器人。
• 检查男嘉宾的出场顺序是否在AI机器人之前（索引更小）。如果不是，说明男嘉宾在机器人之后才登场，无法配对，节目失败。
• 如果顺序正确，两人牵手成功，继续处理下一对。

重复这个过程，直到男嘉宾全部被牵走，或者机器人不够用。如果最后男嘉宾等待区空了，节目成功；否则失败。

---

代码实现（双栈法）

def check_valid_string(s):
    left_stack = []   # 男嘉宾等待区（左括号索引）
    star_stack = []   # AI机器人等待区（星号索引）
    
    for i, ch in enumerate(s):
        if ch == '(':
            left_stack.append(i)          # 男嘉宾入场
        elif ch == '*':
            star_stack.append(i)          # AI机器人入场
        else:  # ch == ')'
            if left_stack:
                left_stack.pop()          # 男嘉宾牵手女嘉宾
            elif star_stack:
                star_stack.pop()          # AI机器人扮男嘉宾牵手
            else:
                return False              # 无人可牵，失败
    
    # 节目结束，处理剩余男嘉宾和AI机器人
    while left_stack and star_stack:
        if left_stack[-1] > star_stack[-1]:  # 男嘉宾在机器人之后登场，无法配对
            return False
        left_stack.pop()
        star_stack.pop()
    
    return len(left_stack) == 0  # 所有男嘉宾都被牵走才算成功

---

用例子模拟节目

例1："(*)"

• 男嘉宾 ( 入场 → 等待区：[0]
• AI机器人 * 入场 → 机器人区：[1]
• 女嘉宾 ) 入场 → 优先用男嘉宾，弹出左栈 → 等待区：[]，机器人区：[1]
• 节目结束，等待区为空 → 成功 ✅

例2："(*))"

• 男嘉宾 ( → [0]
• AI机器人 * → [1]
• 女嘉宾 ) → 弹出左栈 → []，机器人区：[1]
• 女嘉宾 ) → 左栈空，弹出机器人区 → []
• 节目结束，全部配对 → 成功 ✅

例3："*(("

• AI机器人 * → [0]
• 男嘉宾 ( → [1]
• 男嘉宾 ( → [1,2]
• 节目结束，处理剩余：弹出男嘉宾2和机器人0，检查 2 > 0 → 男嘉宾在机器人之后，失败 ❌

---

总结

综艺元素	括号字符串	数据结构
男嘉宾	(	左栈
女嘉宾	)	触发匹配
AI机器人	*	星栈
出场顺序	索引	用于最后校验

双栈法的精髓在于：

1. 实时匹配：遇到右括号时立即处理，不拖泥带水。
2. 延迟决策：星号先存着，需要时再决定角色。
3. 顺序校验：最后必须保证星号（当右括号时）在左括号之后。

希望这期“大型相亲综艺”能帮你彻底搞懂双栈法。下次遇到这道题，闭上眼睛想想男嘉宾、女嘉宾和AI机器人，代码自然就浮现了。

---

作者：小玮

日期：2026-08-30

---

文章写好了，您可以发布到CSDN。如果觉得哪里需要调整，随时告诉我。