当前位置：首页 > article >正文

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

article 2024/10/24 17:48:50

题目链接

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

题目描述

注意

2 <= n <= 10^5
1 <= skills[i] <= 10^6
skills 中的整数互不相同
这个比赛的赢家是第一位连续赢下k场比赛的玩家

解答思路

双指针，一个指针maxIdx指向当前技能等级最高的玩家，另一个指针i从头开始遍历，如果skills[i]等级更高，则更新maxIdx为i，games修改为1；如果skills[i]等级更低，则更新games值，直到找到第一位games达到k的玩家，返回maxIdx
需要注意的是，如果遍历一次仍未找到连续赢K场比赛的玩家，则输掉的玩家都移至末尾，此时maxIdx实际指向的是整个数组中的最大值，且其此时处于数组头部，第二轮连续赢 K 场比赛的第一位玩家一定就是该玩家

代码

class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        int maxIdx = 0;
        int games = 0;
        for (int i = 1; i < skills.length; i++) {
            if (skills[i] > skills[maxIdx]) {
                maxIdx = i;
                games = 1;
            } else {
                games++;
            }
            if (games >= k) {
                return maxIdx;
            }
        }
        return maxIdx;
    }
}