题目链接

找到连续赢 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;
    }
}

关键点

• 双指针的思想
• 如果第一轮未找到连续赢 K 场比赛的第一位玩家，则第二轮满足该条件的玩家一定是maxIdx对应的玩家