LeetCode 649. Dota2 参议院

2026-03-28 HGNULB 约 9 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 649. Dota2 参议院

题意分析

题目目标：字符串 senate 里每个字符代表一位参议员的阵营（R 天辉、D 夜魇）。参议员按下标顺序轮流行使权利，轮完一圈从头再来。每位参议员在轮到自己时可以「禁止」某位还有权利的对手，被禁的人永久出局；如果轮到某人时对方阵营已全部出局，他所在的阵营立即宣布胜利。所有人都足够聪明，问最终哪个阵营获胜。

核心约束：「足够聪明」是全题的题眼——它意味着不需要搜索所有决策组合，一定存在一个可以直接论证的最优策略。另外「轮完一圈从头再来」表明这是循环顺序，实现时必须能表达「下一轮的位置」。$n$ 最大到 $10^4$，而每一轮至少淘汰一人，所以总操作次数天然有界。

边界处理：某一方从一开始就人数为 0 时另一方直接获胜；两方人数相等时先手方（下标更靠前的那一方）通常占优，不能想当然按人数判胜负；同一位参议员在被禁之前可以多次行使权利。

实现取舍：可以用两个队列存下标做「轮转淘汰」，也可以用一个计数器扫描（记录当前累积的禁令数）。前者更贴近题意、更容易讲清楚正确性，后者代码更短但可读性差。面试里推荐前者。

解法：贪心选择

核心思路

先想暴力：每一轮枚举当前参议员该禁谁，搜索所有决策组合，指数级，直接排除。所以必须找到「聪明」的具体含义。

关键在于回答一个问题：轮到某位天辉参议员时，他应该禁掉哪一位夜魇？被禁的人永久失去权利，所以这一次禁令的价值 = 阻止了那个人未来即将造成的伤害。谁的伤害最迫近？当然是在他之后最先轮到的那位对手——因为如果不禁掉此人，此人马上就会行使权利禁掉一位天辉；而更靠后的对手即使暂时不禁，也还来得及在下一轮处理。所以最优策略是：禁掉下一个即将行动的对手。这是一个标准的交换论证：把禁令从「最近的对手」换成「更远的对手」，只会让最近的那位多出手一次，局面不会变好。

有了这条策略，模拟就变得机械了。用两个队列 qr、qd 分别按下标升序保存两方还有权利的参议员。任意时刻，两个队头分别是各自阵营中「下一个将要行动的人」，而队头下标更小的那位先行动，他自然会禁掉对方的队头。

于是不变量是：两个队列内部下标始终升序，队头即为该阵营下一位行动者；每一轮比较队头，小者存活并被追加到自己队列的末尾且下标加 $n$，大者被淘汰。为什么加 $n$：他行使完这一轮的权利后，要等下一圈才能再次行动，而下一圈的「虚拟下标」正是 i + n；因为加的是同一个常数，队列内部的相对顺序不变，升序性质得以保持，这就是为什么可以直接 offer 到队尾而不需要重新排序。

循环终止时必有一方队列为空，非空的那方获胜。每轮循环恰好淘汰一人（弹出两个队头、放回一个），所以最多 $n$ 轮就会结束，不会死循环。

解题步骤

第一步：扫描 senate，把 R 的下标压进 qr、D 的下标压进 qd。 为什么存下标而不是存字符：胜负完全由「谁先轮到」决定，而顺序信息只存在于下标里；存字符会丢掉这个唯一有用的信息。

第二步：当两个队列都非空时循环。 为什么是「都非空」：只要有一方空了，另一方就已经获胜，无需继续。

第三步：比较两个队头。若 qr 的队头更小，说明天辉这位先行动，把 qr.peek() + n 追加到 qr 末尾；否则把 qd.peek() + n 追加到 qd 末尾。 为什么只需比较队头：队列升序，队头就是各自阵营中最先行动的人，全局最先行动的必然是两个队头中下标较小的那位。为什么加 $n$：表示他进入下一圈继续排队，且不破坏队列的升序性。

第四步：两个队头一起出队。 为什么两个都出：先行动者的「当前这一轮」已经用掉了（他的新身份已经以 +n 的形式排在队尾），后行动者则被他禁掉、永久出局。这一步是全题最容易写反的地方——不能只弹出被淘汰的那一个。

第五步：循环结束后，qr 非空返回 "Radiant"，否则返回 "Dire"。

以 senate = "RDD" 走一遍：$n = 3$。初始化后 qr = [0]（下标 0 是 R），qd = [1, 2]（下标 1、2 是 D）。

第 1 轮：队头分别是 0 和 1。0 < 1，天辉的 0 号先行动，他禁掉最近的对手——夜魇的 1 号。把 0 + 3 = 3 追加进 qr，然后两个队头同时出队。结果 qr = [3]，qd = [2]。含义是：0 号天辉将在第二圈（虚拟下标 3）再次行动，1 号夜魇已出局。

第 2 轮：队头分别是 3 和 2。3 < 2 不成立，说明夜魇的 2 号排在天辉的 3 号之前先行动，他禁掉天辉的 3 号。把 2 + 3 = 5 追加进 qd，两个队头同时出队。结果 qr = []，qd = [5]。

循环条件不再满足（qr 已空），返回 "Dire"，与期望一致。直观复盘：0 号 R 先禁掉 1 号 D，但剩下的 2 号 D 紧接着就能禁掉唯一的 R，天辉再无翻身机会。

再以 senate = "RD" 走一遍：qr = [0]，qd = [1]。第 1 轮队头 0 与 1，0 < 1，天辉先手禁掉夜魇，qr 变成 [2]，qd 变成 []。循环结束，返回 "Radiant"。这个用例说明人数相同时先手方获胜，印证了「不能按人数判胜负」这条边界。

代码实现

class Solution {
    public String predictPartyVictory(String senate) {
        int n = senate.length();
        Deque<Integer> qr = new ArrayDeque<>();
        Deque<Integer> qd = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            if (senate.charAt(i) == 'R') {
                qr.offer(i);
            } else {
                qd.offer(i);
            }
        }
        while (!qr.isEmpty() && !qd.isEmpty()) {
            if (qr.peek() < qd.peek()) {
                qr.offer(qr.peek() + n);
            } else {
                qd.offer(qd.peek() + n);
            }
            qr.poll();
            qd.poll();
        }
        return qr.isEmpty() ? "Dire" : "Radiant";
    }
}

func predictPartyVictory(senate string) string {
    n := len(senate)
    qr := []int{}
    qd := []int{}
    for i, c := range senate {
        if c == 'R' {
            qr = append(qr, i)
        } else {
            qd = append(qd, i)
        }
    }
    for len(qr) > 0 && len(qd) > 0 {
        r, d := qr[0], qd[0]
        qr, qd = qr[1:], qd[1:]
        if r < d {
            qr = append(qr, r+n)
        } else {
            qd = append(qd, d+n)
        }
    }
    if len(qr) > 0 {
        return "Radiant"
    }
    return "Dire"
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每轮循环弹出两个元素、最多放回一个，队列中的元素总数严格减少 1，初始总数为 $n$，因此循环至多执行 $n$ 轮；每轮只有常数次队列操作。

空间复杂度：$O(n)$。凭什么：两个队列合起来保存全部参议员的下标，元素总数从 $n$ 开始单调递减，峰值即为 $n$；没有额外的递归或矩阵。

关键点总结

「所有人都足够聪明」意味着存在可论证的最优策略，任务是找出它而不是搜索它。 本题的策略是「禁掉下一个即将行动的对手」，靠交换论证证明：换成更远的对手只会让更近的那位多出一次手。

循环轮转用「下标 + n」表达，比取模更好用。 加常数保持了队列的相对顺序，使得直接追加到队尾就天然有序，省掉了排序或双端插入。

两个有序队列比较队头，是「谁先行动」这类调度问题的通用建模。 同样的骨架可以套到多路归并、任务调度、双方轮流取数等场景。

每轮必须同时弹出两个队头。 一个是「用掉了本轮权利」，一个是「被淘汰」，只弹一个会让局面停滞甚至死循环。

胜负不能按两方人数判断。 "RD" 中双方各一人，先手获胜，这个反例足以否定任何基于计数的直觉解法。

面试视角：先讲清「聪明」的含义并给出交换论证，再说「用两个升序队列表示各自的行动顺序」，最后写模拟。面试官常追问「为什么加 $n$ 而不是取模」——答案是加 $n$ 保证队列仍然升序、可以直接追加，而取模会破坏顺序需要额外维护轮次。另一个常见追问是复杂度，要能说出「每轮净减一人，所以是 $O(n)$」。

易错点总结

错误写法：只弹出被淘汰的那一方，胜者留在队头不出队 → 用例 "RD"，第 1 轮天辉 0 号获胜后仍在队头，qd 空了循环结束返回 "Radiant" 碰巧正确；换成 "RDD"，天辉 0 号永远停在队头且反复与 qd 的队头比较，qr 中被不断追加 3, 3, 3...，队列无限增长直至内存溢出。

错误写法：胜者重新入队时不加 n，直接 offer(qr.peek()) → 用例 "RDD"，qr 变成 [0] 而 qd 是 [2]，0 < 2 天辉又胜，qd 清空返回 "Radiant"，而期望是 "Dire"；根本原因是同一位参议员在同一圈内被允许重复行动。

错误写法：入队时用 (i + n) % n 取模 → 取模后下标回到原值，与上一条等价，同样让参议员在本圈内重复出手。

错误写法：比较写成 qr.peek() <= qd.peek() 或 > 方向反了 → 下标互不相同，<= 与 < 等价不影响结果；但若写成 qr.peek() > qd.peek() 时让天辉获胜，用例 "RD" 会返回 "Dire"，与期望相反。

错误写法：先出队再比较，且比较用的是出队后的新队头 → 用例 "RDD"，第 1 轮弹出 0 和 1 之后拿 qr 的新队头（空）与 qd 的新队头 2 比较，直接抛空指针或越界异常。

错误写法：循环条件写成 || → 用例 "RD"，第 1 轮后 qd 已空但循环继续，qd.peek() 在空队列上返回 null 触发拆箱空指针异常。

错误写法：按两方人数多少直接判胜负 → 用例 "RD" 与 "DR" 的人数完全相同（各 1 人），按人数只能判成平局，而正确答案分别是 "Radiant" 和 "Dire"——胜负由谁的下标更靠前决定，与人数无关。

错误写法：队列里存字符而非下标 → 丢失顺序信息，无法判断谁先行动，只能退回按人数比较，见上一条。

错误写法：用 List.remove(0) 模拟出队 → 用例 $n = 10^4$，每次删除头部是 $O(n)$ 的元素搬移，总复杂度退化为 $O(n^2)$，大数据下超时；应使用 ArrayDeque 或切片。

错误写法：把返回值写成 "radiant" / "DIRE" 等大小写不符的字符串 → 判题按精确字符串比较，直接失败。

相似题目

题目	难度	考察点
316. 去除重复字母	中等	贪心依据是字典序，还要额外统计剩余出现次数来判断能否安全弹出
402. 移掉 K 位数字	中等	用单调栈实现「淘汰」，淘汰次数由 k 给定而非由对抗过程决定
621. 任务调度器	中等	同样是轮次调度，但答案可由最高频任务直接推公式，无需真的模拟每一轮