3175.找到连续赢 K 场比赛的第一位玩家

【LetMeFly】3175.找到连续赢 K 场比赛的第一位玩家:一次遍历(记录胜者)——清晰题解

力扣题目链接:https://leetcode.cn/problems/find-the-first-player-to-win-k-games-in-a-row/

有 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 中的整数互不相同。

解题方法:擂台调整-一次遍历

首先需要明白:

  1. 一个人若是失败一场,则他将永无出头之日,永远作为一个失败者(因此失败后他的值不再重要,不用真的把他移动到队尾,他只是一个给强者刷等级的小喽啰)
  2. 若是每人都比过一次还无k连胜胜者,则其中的最强之人将会霸榜,每人能将他拿下(因此不论k多大,最终k连胜者一定是他)

所以解题思路来了:

  1. 使用$winner$记录遍历过程中最强者下标,使用$challenger$记录当前被遍历到的人的下标,使用$cnt$记录$winner$的连胜场数。
  2. 遍历过程中,若$skills[winner]\gt skills[challenger]$则连胜累积($cnt+=1$);否则江山易主(令$winner$为$challenger$并将连胜局数重置为$1$)
  3. 结束条件:出现k连胜者或者遍历结束。结束后返回$winner$。

时空复杂度:

  • 时间复杂度$O(len(skills))$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int findWinningPlayer(vector<int>& skills, int k) {
int winner = 0;
for (int challenger = 1, cnt = 0; challenger < skills.size() && cnt < k; challenger++) {
if (skills[winner] > skills[challenger]) {
cnt++;
} else {
winner = challenger;
cnt = 1;
}
}
return winner;
}
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main

func findWinningPlayer(skills []int, k int) int {
winner := 0
for challenger, cnt := 1, 0; challenger < len(skills) && cnt < k; challenger++ {
if skills[winner] > skills[challenger] {
cnt++;
} else {
winner = challenger
cnt = 1
}
}
return winner
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int findWinningPlayer(int[] skills, int k) {
int winner = 0;
for (int challenger = 1, cnt = 0; challenger < skills.length && cnt < k; challenger++) {
if (skills[winner] > skills[challenger]) {
cnt++;
} else {
winner = challenger;
cnt = 1;
}
}
return winner;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List

class Solution:
def findWinningPlayer(self, skills: List[int], k: int) -> int:
winner, challenger, cnt = 0, 1, 0
while challenger < len(skills) and cnt < k:
if skills[winner] > skills[challenger]:
cnt += 1
else:
winner = challenger
cnt = 1
challenger += 1
return winner

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/143206596


3175.找到连续赢 K 场比赛的第一位玩家
https://blog.letmefly.xyz/2024/10/24/LeetCode 3175.找到连续赢K场比赛的第一位玩家/
作者
Tisfy
发布于
2024年10月24日
许可协议