Medium

题目描述

一场比赛由编号从 0 到 n - 1 的 n 个玩家组成。

给你一个长度为 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 <= 10^5
  • 1 <= k <= 10^9
  • 1 <= skills[i] <= 10^6
  • skills 中的所有整数都是唯一的

解题思路

这道题有两种思路来解决：

思路1：暴力模拟（适用于小k） 直接按照题目描述模拟比赛过程，使用队列来维护玩家顺序。每次让队首两个玩家比赛，赢者留在队首，败者移到队尾，并记录当前队首玩家的连胜次数。当连胜次数达到k时返回该玩家索引。

思路2：优化分析（推荐解法） 关键观察：如果k >= n-1，那么答案必定是技能值最大的玩家，因为他一旦到达队首就会一直获胜。

对于k < n-1的情况，我们可以优化模拟过程：

  1. 维护当前的"擂主"（队首玩家）和他的连胜次数
  2. 遍历后续玩家，如果能击败擂主，就成为新擂主，连胜次数重置为1
  3. 如果不能击败擂主，擂主连胜次数+1
  4. 当连胜次数达到k时，返回当前擂主

这种方法避免了实际的队列操作，时间复杂度从O(nk)优化到O(n)。

核心思想是：一旦某个玩家连续击败了k个对手，或者他是技能最强且k足够大，他就是最终赢家。

代码实现

class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        int n = skills.length;
        if (k >= n - 1) {
            return max_element(skills.begin(), skills.end()) - skills.begin();
        }
        
        int currentWinner = 0;
        int winCount = 0;
        
        for (int i = 1; i < n; i++) {
            if (skills[currentWinner] > skills[i]) {
                winCount++;
            } else {
                currentWinner = i;
                winCount = 1;
            }
            
            if (winCount == k) {
                return currentWinner;
            }
        }
        
        return currentWinner;
    }
};

class Solution:
    def findWinningPlayer(self, skills: List[int], k: int) -> int:
        n = len(skills)
        if k >= n - 1:
            return skills.index(max(skills))
        
        current_winner = 0
        win_count = 0
        
        for i in range(1, n):
            if skills[current_winner] > skills[i]:
                win_count += 1
            else:
                current_winner = i
                win_count = 1
            
            if win_count == k:
                return current_winner
        
        return current_winner

public class Solution {
    public int FindWinningPlayer(int[] skills, int k) {
        int n = skills.Length;
        if (k >= n - 1) {
            int maxIndex = 0;
            for (int i = 1; i < n; i++) {
                if (skills[i] > skills[maxIndex]) {
                    maxIndex = i;
                }
            }
            return maxIndex;
        }
        
        int currentWinner = 0;
        int winCount = 0;
        
        for (int i = 1; i < n; i++) {
            if (skills[currentWinner] > skills[i]) {
                winCount++;
            } else {
                currentWinner = i;
                winCount = 1;
            }
            
            if (winCount == k) {
                return currentWinner;
            }
        }
        
        return currentWinner;
    }
}

var findWinningPlayer = function(skills, k) {
    let currentWinner = 0;
    let consecutiveWins = 0;
    
    for (let i = 1; i < skills.length; i++) {
        if (skills[currentWinner] > skills[i]) {
            consecutiveWins++;
        } else {
            currentWinner = i;
            consecutiveWins = 1;
        }
        
        if (consecutiveWins === k) {
            return currentWinner;
        }
    }
    
    return currentWinner;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 最多遍历一次数组
空间复杂度O(1) - 只使用常数额外空间