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

---

解题分析及思路：

方法：模拟

思路：

直接模拟：

1. 定义一个守擂玩家 play1 ，初始值为 skills[0]
2. 根据比赛规则，每次都跟守擂玩家进行比赛
   • 如果守擂玩家胜出，则将守擂玩家排到队尾
   • 如果守擂玩家输掉，则将守擂玩家排到队头，同时将守擂玩家更新为当前输掉的玩家
3. 使用两个标记器，分别记录守擂玩家和进攻的玩家，将 num1 标记守擂玩家的编号，当守擂玩家赢取 k 场比赛，则返回守擂玩家的编号
4. 在此过程中，用 count 记录守擂玩家赢取的场次，当守擂玩家赢取 k 场次，则返回守擂玩家的编号
5. 为了减少比赛的场数，当 k 值比队列长度还大，则返回所有元素中最大的玩家编号，可以进一步优化成，当守擂玩家赢取了 len(skills) 场次之后，即代表 k 值大于 len(skills)，返回 num1 即可

func findWinningPlayer(skills []int, k int) int {
	play1 := skills[0]
	skills = skills[1:]
	var count int
	var num1, num2 = 0, 1
	for count < k {
		play2 := skills[0]
		if play1 > play2 {
			count++
			skills = append(skills[1:], play2)
		} else {
			count = 1
			skills = append(skills[1:], play1)
			play1 = play2
			num1 = num2
		}
		num2++
		if count > len(skills) {
			return num1
		}
	}
	return num1
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:10.9 MB,击败了15.79% 的Go用户