LeetCode 649. Dota2 参议院

约 5 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 LeetCode 75
标签
字符串 贪心 队列

题目描述

✅ 649. Dota2 参议院

image-20260928233813975

image-20260928233813976

题意分析

字符串中的 R 和 D 分别代表两个阵营的参议员。仍有权利的议员按原顺序循环行动，每次可以永久禁止另一名议员继续行动；当只剩自己阵营时即可宣布获胜。双方都为本阵营采取最优策略，返回最终阵营全称。

被禁权者不仅跳过本轮，以后也不再参加。人数更多不一定获胜，因为先后行动顺序同样重要；需要跟踪存活者下一次行动的位置，而不是只比较两个字符的数量。

解法：两队列模拟最早行动者禁权

核心思路

[!blue]

当前议员应优先禁止最早即将行动的对方。对方议员的权限相同，区别在于下一次行动时间；若改为禁止更晚的人，就留下更早的反击机会。交换这两个对手的存活身份，相当于把对方的一次行动从早处推迟到晚处，不会让己方失去原本能提前行动的机会，所以优先消除最早威胁不会更差。

分别用两个队列保存 R、D 阵营的下一次行动时刻。初始时刻就是原字符串下标，两个队列各自已经有序。比较两个队首，较小的一方就是下一位能行动的人，另一队的队首正好是它应禁止的最早对手。

本次把两边旧队首都移出：先行动者已经用掉本次机会，后行动者被永久淘汰。只有先行动者再次入队，下一次时刻为原时刻加上固定的原人数 n，表示下一轮同一位置。这样保留循环次序，不需要反复扫描已经被禁权的空位。

重新入队的时刻排在本阵营尚未行动者之后，因此队列继续有序。下一次仍比较两个队首，就能在两个阵营的未来日程中选出最早动作。Java 先追加下一次时刻再弹出旧队首，Go 先弹出再追加，维护的是同一个过程。

每次对决恰好减少一名仍有权利的议员。当某个队列为空，就不再有该阵营的反击者，另一个阵营可以宣布胜利。

解题步骤

  1. 扫描字符串，按下标将两个阵营的议员分别入队。
  2. 两队都非空时，比较最早行动时刻。
  3. 弹出双方旧队首，只将较早行动的一方以旧时刻加 n 放回队尾。
  4. 一方队列为空时，返回另一方的完整名称。

代码实现

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)$。初始化扫描一次；每次对决永久淘汰一人，所以模拟最多进行 n - 1 次，每次只有常数次队列操作。
  • 空间复杂度：$O(n)$，两个队列保存存活议员的未来行动时刻。

关键点总结

[!green]

  • 同阵营议员权限相同，优先禁掉最早对手可以推迟对方的反击机会。
  • 队列存的是未来行动时刻，旧时刻加原人数表示进入下一轮。
  • 每次只有一人重新排队，存活人数严格减少，保证线性次模拟后结束。

易错点总结

[!yellow]

  • 只比较双方人数，忽略了较早行动者可以先淘汰对手。
  • 获胜者仍以旧时刻入队，会让它再次抢在本轮其他人之前行动。
  • 使用当前剩余人数代替原人数推进时刻，会改变循环中的相对位置。
  • 两个出队者都放回队列，会让已禁权者继续参加；两个都不放回则会误删胜者。
  • 返回单个字符而不是 Radiant 或 Dire，不符合输出约定。

相似题目

题目 难度 关联与区别
950. 按递增顺序显示卡牌 中等 同样用队列保存循环顺序，原题按取出再放回的规则生成顺序，本题还要永久淘汰对方队首。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/89728735
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！