Medium

题目描述

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

游戏将在数组的前两个元素之间进行（即 arr[0] 和 arr[1]）。在游戏的每一轮中，我们比较 arr[0] 和 arr[1]，较大的整数获胜并保持在位置 0，较小的整数移动到数组的末尾。当一个整数连续获胜 k 轮时，游戏结束。

返回游戏的获胜者。

题目保证游戏一定会有获胜者。

示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：让我们看看游戏的轮次：
轮次 |       arr       | 获胜者 | 连胜次数
  1  | [2,1,3,5,4,6,7] |   2   |    1
  2  | [2,3,5,4,6,7,1] |   3   |    1
  3  | [3,5,4,6,7,1,2] |   5   |    1
  4  | [5,4,6,7,1,2,3] |   5   |    2
我们可以看到游戏进行了 4 轮，5 是获胜者，因为它连续获胜了 2 场比赛。

示例 2：

输入：arr = [3,2,1], k = 10
输出：3
解释：3 将连续获胜前 10 轮。

约束条件：

  • 2 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^6
  • arr 包含不同的整数
  • 1 <= k <= 10^9

解题思路

这道题目需要模拟数组游戏的过程，但直接模拟会超时。我们需要观察游戏的规律来优化算法。

核心观察：

  1. 如果 k >= arr.length，那么最大元素一定会成为获胜者，因为一旦最大元素到达位置 0，它就会一直获胜
  2. 如果 k < arr.length，我们需要模拟游戏过程，但有一个重要优化：我们不需要真正移动数组元素

优化思路：

  • 维护当前的获胜者（初始为 arr[0]）和连胜次数
  • 遍历数组中的其他元素，与当前获胜者比较
  • 如果遇到更大的元素，更新获胜者并重置连胜次数为 1
  • 如果当前获胜者更大，增加连胜次数
  • 当连胜次数达到 k 或者当前获胜者是数组最大值时，返回结果

这种方法避免了实际的数组操作，时间复杂度从 O(n*k) 降低到 O(n)。

代码实现

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int maxVal = *max_element(arr.begin(), arr.end());
        int winner = arr[0];
        int winCount = 0;
        
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] > winner) {
                winner = arr[i];
                winCount = 1;
            } else {
                winCount++;
            }
            
            if (winCount == k || winner == maxVal) {
                return winner;
            }
        }
        
        return winner;
    }
};

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        max_val = max(arr)
        winner = arr[0]
        win_count = 0
        
        for i in range(1, len(arr)):
            if arr[i] > winner:
                winner = arr[i]
                win_count = 1
            else:
                win_count += 1
            
            if win_count == k or winner == max_val:
                return winner
        
        return winner

public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxVal = arr.Max();
        int winner = arr[0];
        int winCount = 0;
        
        for (int i = 1; i < arr.Length; i++) {
            if (arr[i] > winner) {
                winner = arr[i];
                winCount = 1;
            } else {
                winCount++;
            }
            
            if (winCount == k || winner == maxVal) {
                return winner;
            }
        }
        
        return winner;
    }
}

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var getWinner = function(arr, k) {
    let current = arr[0];
    let wins = 0;
    
    for (let i = 1; i < arr.length; i++) {
        if (current > arr[i]) {
            wins++;
        } else {
            current = arr[i];
            wins = 1;
        }
        
        if (wins === k) {
            return current;
        }
    }
    
    return current;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，寻找最大值需要 O(n) 时间
空间复杂度O(1)只使用常数级别的额外空间