---

1535. 找出数组游戏的赢家

• 标签：数组、模拟
• 难度：中等

题目链接

• 1535. 找出数组游戏的赢家 - 力扣

题目大意

描述：给定一个由不同整数组成的数组 $arr$ 和一个整数 $k$。有一个游戏规则：

• 初始时，比较 $arr[0]$ 和 $arr[1]$，较大的元素获胜，较小的元素移到数组末尾。
• 下一轮，用获胜元素和数组中的下一个元素比较。
• 当一个元素连续获胜 $k$ 轮时，游戏结束。

要求：返回最终的获胜元素。

说明：

• $2 \le arr.length \le 10^5$。
• $1 \le arr[i] \le 10^6$。
• $1 \le k \le 10^9$。

示例：

• 示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况：
![](https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/07/30/q-example.png)
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

• 示例 2：

输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

解题思路

思路 1：模拟 + 一次遍历

1. 核心思想

不需要真的移动数组元素。只需一次遍历，维护当前"擂主"和获胜次数。

关键观察：

• 如果 $k \ge n$，则最终获胜者一定是数组中的最大值（因为最大值早晚会遇到所有其他元素，且永不失败）。
• 在遍历过程中，如果某个元素连续获胜 $k$ 次，直接返回。

2. 具体步骤

第 1 步：设 $winner = arr[0]$，$count = 0$。

第 2 步：从 $i = 1$ 遍历到 $n-1$：

• 如果 $winner > arr[i]$：$count += 1$。
• 否则：$winner = arr[i]$，$count = 1$。
• 如果 $count == k$，返回 $winner$。

第 3 步：遍历结束仍未返回，说明 $k \ge n$，返回数组中的最大值（即 $winner$）。

3. 正确性证明

• 最大值永远不会被击败，因此一旦最大值成为 $winner$，会一直保持。
• 如果 $k < n$，在遍历完数组之前一定会遇到连续赢 $k$ 次的情况。
• 因为每次失败者被移到末尾，而 $winner$ 与下一个元素比较。遍历顺序就是实际比赛顺序。

4. 举例说明

以 $arr = [2,1,3,5,4,6,7], k = 2$ 为例：

• $winner=2$，$count=0$。
• $i=1$：$2 > 1$，$count=1$。
• $i=2$：$2 < 3$，$winner=3$，$count=1$。
• $i=3$：$3 < 5$，$winner=5$，$count=1$。
• $i=4$：$5 > 4$，$count=2$，返回 $5$。

以 $arr = [3,2,1], k = 10$ 为例：

• $winner=3$，$count=0$。
• $i=1$：$3 > 2$，$count=1$。
• $i=2$：$3 > 1$，$count=2$。
• 遍历结束，$k=10$ 但 $count < k$，返回 $3$（最大值）。

思路 1：代码

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        winner = arr[0]
        count = 0

        for i in range(1, n):
            if winner > arr[i]:
                count += 1
            else:
                winner = arr[i]
                count = 1
            if count == k:
                return winner

        return winner

思路 1：复杂度分析

• 时间复杂度：$O(n)$，一次遍历。
• 空间复杂度：$O(1)$。