LeetCode 题解工作台
找到连续赢 K 场比赛的第一位玩家
有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。 给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。 skills 中所有整数 互不相同 。 所有玩家从编号 0 到 n - 1 排成一列。 比赛进行方式如下： …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·模拟
答案摘要
我们注意到，每次会比较数组的前两个元素，不管结果怎么样，下一次的比较，一定是轮到了数组中的下一个元素和当前的胜者进行比较。因此，如果循环了 次，那么最后的胜者一定是数组中的最大元素。否则，如果某个元素连续胜出了 次，那么这个元素就是最后的胜者。 时间复杂度 ，其中 是数组的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·模拟 题型思路
题目描述
有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。
给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。
所有玩家从编号 0 到 n - 1 排成一列。
比赛进行方式如下：
- 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
- 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。
请你返回这个比赛的赢家编号。
示例 1：
输入：skills = [4,2,6,3,9], k = 2
输出：2
解释：
一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下：
- 玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为
[0,2,3,4,1]。 - 玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为
[2,3,4,1,0]。 - 玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为
[2,4,1,0,3]。
玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。
示例 2：
输入：skills = [2,5,4], k = 3
输出：1
解释：
一开始，队列里的玩家为 [0,1,2] 。比赛过程如下：
- 玩家 0 和 1 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为
[1,2,0]。 - 玩家 1 和 2 进行一场比赛，玩家 1 的技能等级高于玩家 2 ，玩家 1 胜出，队列变为
[1,0,2]。 - 玩家 1 和 0 进行一场比赛，玩家 1 的技能等级高于玩家 0 ，玩家 1 胜出，队列变为
[1,2,0]。
玩家 1 连续赢了 k = 3 场比赛，所以赢家是玩家 1 。
提示：
n == skills.length2 <= n <= 1051 <= k <= 1091 <= skills[i] <= 106skills中的整数互不相同。
解题思路
方法一：脑筋急转弯
我们注意到，每次会比较数组的前两个元素，不管结果怎么样，下一次的比较，一定是轮到了数组中的下一个元素和当前的胜者进行比较。因此，如果循环了 次，那么最后的胜者一定是数组中的最大元素。否则，如果某个元素连续胜出了 次，那么这个元素就是最后的胜者。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
相似题目：
class Solution:
def findWinningPlayer(self, skills: List[int], k: int) -> int:
n = len(skills)
k = min(k, n - 1)
i = cnt = 0
for j in range(1, n):
if skills[i] < skills[j]:
i = j
cnt = 1
else:
cnt += 1
if cnt == k:
break
return i
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) in the worst case when simulating until a player reaches k wins, since each player is compared at most once per match. Space complexity is O(1) if only counters and indices are used without an explicit queue. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you tracking consecutive wins correctly?
- question_mark
Consider the maximum skill shortcut when k is very large.
- question_mark
Check for off-by-one errors when updating the streak and winner.
常见陷阱
外企场景- error
Resetting the streak incorrectly when the winner changes.
- error
Failing to handle the case when k >= n efficiently.
- error
Modifying the array instead of using indices, leading to unnecessary overhead.
进阶变体
外企场景- arrow_right_alt
Return the list of players who reach k wins first in multiple simulations.
- arrow_right_alt
Compute the number of matches needed for the first player to reach k wins.
- arrow_right_alt
Handle ties in skill levels and determine who reaches k wins first under tie rules.