649. Dota2 参议院

🎯 问题描述

描述：
Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）。参议院由来自两派的参议员组成。现在他们要对游戏中的改变进行投票。投票过程是轮次的，每位参议员可以行使两项权利之一：

禁止一名参议员的权利：使另一名参议员在后续所有轮次中失去投票权。
宣布胜利：如果当前轮次中，有投票权的参议员都来自同一个阵营，那么他可以宣布胜利。

给定一个代表每个参议员阵营的字符串 senate（‘R’ 代表 Radiant，‘D’ 代表 Dire），假设每位参议员都会为自己的阵营做出最明智的选择（即优先禁止对自己阵营威胁最大的敌方参议员）。你需要预测最终哪一方会宣布胜利。

说明：

这是一个队列模拟与贪心问题。
核心策略：
- 参议员按照字符串顺序轮流行动。
- 最明智的选择是：禁止掉下一个即将行动的敌方参议员。因为如果不禁止，对方下一轮就会禁止自己阵营的队友。
- 使用队列模拟轮流行动的过程，每次行动时直接在队列中寻找并移除敌方参议员。
示例：
示例 1：

输入：senate = "RD"
输出："Radiant"
解释：
第1轮：R先行动，禁止掉D的权利。D失去权利。
第2轮：只剩下R有权利，R宣布胜利。

💻 解题思路

思路1：队列模拟 + 贪心淘汰

核心逻辑

初始化：
- 将字符串 senate 转换为双端队列 s，模拟参议员的行动顺序。
轮流行动：
- 只要队列中不止一个阵营的参议员（即队列长度 > 1，且双方都还有人），就持续进行轮次。
- 每次取出队首的参议员 candidate 作为当前行动者。
执行禁止操作（贪心策略）：
- 如果当前行动者是 ‘R’，他需要禁止一名 ‘D’。使用 s.remove("D") 直接移除队列中第一个遇到的 ‘D’（即下一个即将行动的敌方）。
- 如果当前行动者是 ‘D’，他需要禁止一名 ‘R’。使用 s.remove("R") 直接移除队列中第一个遇到的 ‘R’。
- 提前终止：如果在尝试移除敌方时抛出异常（即队列中已经没有敌方了），说明当前阵营已经获胜，直接返回结果。
进入下一轮：
- 成功禁止敌方后，当前行动者本轮任务完成，将其重新加入队尾 s.append(candidate)，等待下一轮行动。
返回最终胜者：
- 循环结束后，队列中剩下的最后一名参议员即为胜者。

代码实现

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        # 将字符串转换为双端队列，模拟参议员的行动顺序
        s = deque(senate)
        
        # 只要队列中还有超过1个元素（意味着双方可能都还有人，或者只剩一人即将胜利）
        while len(s) > 1:
            # 当前行动的参议员出队
            candidate = s.popleft()
            
            if candidate == "R":
                # R 阵营行动，尝试禁止掉队列中下一个 D 阵营的参议员
                try:
                    s.remove("D")
                except ValueError:
                    # 如果队列中已经没有 D 了，说明 R 阵营直接获胜
                    return "Radiant"
            else:
                # D 阵营行动，尝试禁止掉队列中下一个 R 阵营的参议员
                try:
                    s.remove("R")
                except ValueError:
                    # 如果队列中已经没有 R 了，说明 D 阵营直接获胜
                    return "Dire"
            
            # 成功禁止敌方后，当前参议员本轮任务完成，排到队尾等待下一轮
            s.append(candidate)
        
        # 循环结束，队列中剩下的最后一人即为胜者
        ans = s.popleft()
        return "Radiant" if ans == "R" else "Dire"

📊 性能分析

时间复杂度： $O(N^2)$ $O (N^{2})$
- 在最坏情况下（例如 “RDRDRD…” 这种交替排列），每一轮淘汰一个参议员，需要进行 $N$ 轮。
- 队列的 remove() 操作需要遍历查找目标元素，平均时间复杂度为 $O(N)$ 。
- 因此总体时间复杂度为 $O(N^2)$ 。对于本题的数据规模（ $N \le 10^4$ ），该解法是可以接受的。
空间复杂度： $O(N)$ $O (N)$
- 需要一个双端队列来存储 $N$ 个参议员。

思考

为什么使用 try...except？
- 代码巧妙地利用了 Python 列表/队列 remove() 方法的特性：如果找不到目标元素，会抛出 ValueError 异常。
- 这正好对应了“如果队列中已经没有敌方参议员，当前阵营直接获胜”的逻辑，避免了在每次行动前额外遍历检查敌方是否还存在。
贪心策略的正确性：
- 为什么直接 remove 掉队列中第一个遇到的敌方就是最优解？
- 因为队列是按行动顺序排列的，第一个遇到的敌方就是下一个即将行动的敌人。如果不禁止他，他下一轮就会禁止我方队友。因此，优先消灭“眼前”的威胁是最明智的。

思路2：双队列模拟

核心逻辑

在方法一中，我们使用一个队列并不断进行 remove() 操作，这导致了较高的时间复杂度。
优化思路：既然参议员只分 R 和 D 两个阵营，我们可以用两个独立的队列分别存储他们。

初始化：
- 创建两个队列 radiant 和 dire。
- 遍历字符串 senate，将 R 和 D 的**原始下标（索引）**分别存入对应的队列中。
模拟对决（贪心策略）：
- 只要两个队列都不为空，就持续进行对决。
- 每次取出两个队列的队首元素（即当前双方阵营中，最先获得行动权的参议员）。
- 比较下标：
  - 如果 radiant[0] < dire[0]：说明 R 阵营的这位参议员行动顺序更靠前。他可以行使权利，禁止掉 D 阵营的这位参议员（D 队首出队，不再回来）。
  - 获胜的 R 参议员本轮任务完成，需要进入下一轮。为了保持相对顺序，我们将他的下标加上 n（字符串总长度），然后重新加入 radiant 队列的队尾。
  - 反之同理，如果 dire[0] 更小，则 D 获胜并进入下一轮（下标 + n），R 被淘汰。
判断胜负：
- 循环结束时，必定有一个队列为空。非空的那个队列对应的阵营即为胜者。

代码实现

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        # 1. 初始化两个队列，分别存储 R 和 D 参议员的原始下标
        radiant = deque()
        dire = deque()
        
        for i, ch in enumerate(senate):
            if ch == "R":
                radiant.append(i)
            else:
                dire.append(i)
        
        # 2. 模拟对决过程
        while radiant and dire:
            # 比较双方队首参议员的下标（即行动顺序）
            if radiant[0] < dire[0]:
                # R 先行动，R 存活并进入下一轮（下标 + n），D 被淘汰
                radiant.append(radiant[0] + n)
            else:
                # D 先行动，D 存活并进入下一轮（下标 + n），R 被淘汰
                dire.append(dire[0] + n)
            
            # 双方队首元素完成本轮对决，全部出队
            radiant.popleft()
            dire.popleft()
        
        # 3. 返回非空队列对应的阵营
        return "Radiant" if radiant else "Dire"

📊 性能分析

时间复杂度：O(N)
- 初始化遍历字符串需要 O(N)。
- 在 while 循环中，每次循环都会淘汰一名参议员（出队且不再入队）。由于总共有 N 名参议员，最多进行 N 次淘汰操作。
- 队列的 popleft() 和 append() 都是 O(1) 的操作。
- 因此，总体时间复杂度为线性的 O(N)。
空间复杂度：O(N)
- 需要两个队列来存储 N 个参议员的下标。

思考与对比

为什么要给下标加上 n？
- 题目中的投票是轮次制的。第一轮结束后，存活的参议员会进入第二轮，且相对顺序不变。
- 给下标加上 n 是一种巧妙的数学技巧，它既保留了参议员在下一轮的相对先后顺序，又通过一个统一的数值空间（0 到 2n-1）让我们可以持续比较谁先行动，而无需真正去维护“第几轮”的状态。
与方法一（单队列暴力删除）的对比：
- 方法一：逻辑直观，但 s.remove() 需要遍历查找，最坏情况是 O(N²)。
- 方法二：逻辑稍微抽象一点（引入了下标偏移），但完全避免了查找操作，性能极其稳定，是处理此类“循环淘汰”问题的标准最优解。
贪心的本质：
- 两个队列的队首元素，代表了当前全局最早能行动的 R 和最早能行动的 D。
- 他们之间的对决，天然就符合“优先消灭下一个即将行动的敌人”这一最优策略。