3175. 找到连续赢 K 场比赛的第一位玩家
题目描述¶
关联：https://leetcode.cn/problems/find-the-first-player-to-win-k-games-in-a-row/description/
本题的考点是双端队列的使用。
题目描述
有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。
给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同。
所有玩家从编号 0 到 n - 1 排成一列。
比赛进行方式如下：
- 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
- 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。
请你返回这个比赛的赢家编号。
解题思路¶
首先想到的自然是直接模拟，只需要分为两种情况：
- \(k \geq n\)：直接返回技能最大的玩家编号
- \(k < n\)：模拟比赛，直到有玩家连续赢了 \(k\) 场比赛
\(k \geq n\) 的情况就不说了，只需要 return skills.index(max(skills)) 即可。
而 \(k < n\) 的情况，我们可以使用一个队列来模拟比赛，每次比赛都是队列的前两位进行比赛，然后将胜者放到队列的最前面，失败者放到队列的最后面，直到有玩家连续赢了 \(k\) 场比赛。
def k_less_than_n(skills: list[int], k: int) -> int:
queue = list(range(len(skills)))
current_winner = queue[0]
consecutive_wins = 0
while consecutive_wins < k:
player1 = queue.pop(0)
player2 = queue.pop(0)
if skills[player1] > skills[player2]:
current_winner = player1
queue.append(player2)
consecutive_wins += 1
else:
current_winner = player2
queue.append(player1)
consecutive_wins = 1
queue.insert(0, current_winner)
return current_winner
但是这个算法的时间复杂度是 \(O(n^2)\)，会超时。原因在于 list 的 pop(0) 的时间复杂度是 \(O(n)\)，我们可以使用一个双端队列（deque）来优化这个算法。
def k_less_than_n(skills: list[int], k: int) -> int:
queue = deque(range(len(skills)))
current_winner = queue[0]
consecutive_wins = 0
while consecutive_wins < k:
player1 = queue.popleft()
player2 = queue.popleft()
if skills[player1] > skills[player2]:
current_winner = player1
queue.append(player2)
consecutive_wins += 1
else:
current_winner = player2
queue.append(player1)
consecutive_wins = 1
queue.appendleft(current_winner)
return current_winner
popleft 和 appendleft 操作的时间复杂度为 \(O(1)\)，从而提高了效率。
完整题解¶
class Solution:
def findWinningPlayer(self, skills: list[int], k: int) -> int:
n = len(skills)
if k >= n:
return self.k_greater_than_n(skills, k)
else: # k < n
return self.k_less_than_n(skills, k)
def k_less_than_n(self, skills: list[int], k: int) -> int:
queue = deque(range(len(skills)))
current_winner = queue[0]
consecutive_wins = 0
while consecutive_wins < k:
player1 = queue.popleft()
player2 = queue.popleft()
if skills[player1] > skills[player2]:
current_winner = player1
queue.append(player2)
consecutive_wins += 1
else:
current_winner = player2
queue.append(player1)
consecutive_wins = 1
queue.appendleft(current_winner)
return current_winner
def k_greater_than_n(self, skills: list[int], k: int) -> int:
return skills.index(max(skills))
复杂度分析¶
时间复杂度：\(O(n)\)，其中 \(n\) 是 skills 的长度。
空间复杂度：\(O(n)\)，使用了一个双端队列。