深色模式
3175-找到连续赢 K 场比赛的第一位玩家
题目参考: 3175.找到连续赢 K 场比赛的第一位玩家
题目描述
有 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.length
2 <= n <= 105
1 <= k <= 109
1 <= skills[i] <= 106
skills 中的整数互不相同。题解
别被迷惑，题目中说要将比较后的数据移动带最后面，这个操作是不需要的，因为题目中没有说要让我们给出最后序列是什么样的。可做如下思考：
设 maxNum 的序号为 maxNumIndex
- 如果 k >= maxNumIndex, 则当找到 maxNum 時，其在首位的位置不会再变化，此时返回 maxNumIndex
- 如果 k < maxNumIndex, 则按照题目规则，通过双指针查找即可，直到找到 maxNum ，程序停止，返回 maxNumIndex
复杂度分析：
- 时间复杂度：
- 空间复杂度：
py
class Solution(object):
def findWinningPlayer(self, skills, k):
"""
:type skills: List[int]
:type k: int
:rtype: int
"""
length = len(skills)
maxNumIndex = 0
maxNum = skills[0]
for i in range(1, length):
if skills[i] > maxNum:
maxNum = skills[i]
maxNumIndex = i
# 如果 k > maxNumIndex， 则在找到 maxNum 之前不可能找到 第 k 大的数， 直接返回 maxNumIndex
if k > maxNumIndex:
return maxNumIndex
# 在 maxNumIndex 之前查找，不需要移动，采用指针
p = 0
q = 1
count = 0
num = skills[0]
while p < maxNumIndex and q < maxNumIndex:
if count == k:
return p
if skills[p] > skills[q]:
count += 1
q += 1
else:
count = 1
p = q
q += 1
if count == k:
return p
return maxNumIndex