What is the winner in 'Find the Winner of an Array Game' if k is very large?

If k is equal to or exceeds the array length, the winner is the maximum element, as it will inevitably win k consecutive rounds.

Can I simulate the game using extra arrays or queues?

Yes, but it's unnecessary. Tracking only the current winner and consecutive wins achieves O(1) space, which is more efficient.

How does the array plus simulation pattern apply here?

The problem directly uses pairwise comparisons in an array to simulate the game's progress, embodying the array plus simulation pattern.

What if multiple elements tie in consecutive wins?

The rules guarantee distinct integers, so ties cannot occur in consecutive win counts, simplifying simulation logic.

Is there a shortcut instead of full simulation for small arrays?

Yes, for small arrays or when k >= arr.length, returning the maximum element immediately avoids full iteration.

#1535

Medium

auto_awesome数组·模拟

LeetCode 题解工作台

找出数组游戏的赢家

给你一个由不同整数组成的整数数组 arr 和一个整数 k 。每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合…

数组模拟

题目描述

给你一个由不同整数组成的整数数组 arr 和一个整数 k 。

每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的赢家。

返回赢得比赛的整数。

题目数据保证游戏存在赢家。

示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况：

因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

示例 2：

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

示例 3：

输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

示例 4：

输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99

提示：

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr 所含的整数 各不相同 。
1 <= k <= 10^9

lightbulb

解题思路

方法一：脑筋急转弯

我们注意到，每次会比较数组的前两个元素，不管结果怎么样，下一次的比较，一定是轮到了数组中的下一个元素和当前的胜者进行比较。因此，如果循环了 $n-1$ 次，那么最后的胜者一定是数组中的最大元素。否则，如果某个元素连续胜出了 $k$ 次，那么这个元素就是最后的胜者。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

相似题目：

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        mx = arr[0]
        cnt = 0
        for x in arr[1:]:
            if mx < x:
                mx = x
                cnt = 1
            else:
                cnt += 1
            if cnt == k:
                break
        return mx

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element can be compared at most once before the maximum element secures k wins. Space complexity is O(1) since the array is updated in-place and only counters are maintained.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Will you simulate each round or find a shortcut based on k?
question_mark
How do you handle extremely large k values without full simulation?
question_mark
Can you optimize the solution to constant space without extra data structures?

warning

常见陷阱

外企场景

error
Failing to reset the consecutive win count when the leading element loses.
error
Not handling cases where k exceeds array length, leading to unnecessary iterations.
error
Using extra space unnecessarily instead of tracking only the current winner and count.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the first element to reach m consecutive wins in a modified array game.
arrow_right_alt
Determine the winner when the comparison rule is based on modulo values instead of direct magnitude.
arrow_right_alt
Extend the game to allow multiple elements to compete in each round and track the first to reach k wins.

help

常见问题

外企场景

继续练习

#1560 圆形赛道上经过次数最多的扇区 #1562 查找大小为 M 的最新分组 #1503 所有蚂蚁掉下来前的最后一刻