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

题目

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

解题

直接按照题目使用模拟的思路，会导致超时；对 k>skills.length() 的情况直接返回具有 maxSkill 的 index 能够解决这个模拟方法的超时问题。

下面分析一下题目中隐含的一些思路

1. 如果 1 个 player 后面的 t 个 players 的 skill 值都比他低，那么这个 player 至少能够连续赢 t 次。
   1. 当这个 player 是数组中首个 player（即 idx=0），那么这个 player 能够连续赢 t 次。
   2. 如果这个 player 不在第一个位置，那么这个 player 开始第一次比赛时，一定能够将左侧的 player 给打败，所以能够连续赢 t+1 次。
2. player i 在连续赢了 t 次之后，被击败的这些 player 都不需要再去考虑了，他们即使能够击败一些 palyer，但是不能击败连 player-i 都无法击败的人，所以连胜数一定不会满足题意。

1.双指针解法（代码未优化）

class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        // 表示 left 指针
        int left = 0;
        // 计算 maxSkill 所在的 maxIndex 位置
        int maxIndex = skills.length - 1;         // 初始化位置选择最后一个元素
        int maxSkill = skills[skills.length - 1]; // 这样可以简化接下来的遍历流程

        while (left < skills.length - 1) {
            if (skills[left] > maxSkill) {
                maxSkill = skills[left];
                maxIndex = left;
            }
            // 初始化 right 指针
            int right = left + 1;
            // 如果 left 位置能赢，就继续观察它能连续赢多少次
            if (skills[right] < skills[left]) {
                while (right < skills.length) {
                    if (skills[right] > skills[left]) {
                        break;
                    }
                    right++;
                }
                // 如果 left 玩家并非首个玩家，那么 left 不仅需要考虑右侧连续能够赢的玩家数，还要加上一个左侧将会被淘汰的玩家
                int count = left == 0 ? right - left - 1 : right - left;
                if (count >= k) {
                    return left;
                }
                // 玩家 left 连续赢的次数未达到 k 的要求
                // 那么玩家 left 到玩家 right 之间的玩家更加无法达到
                // 所以更新 left 为 right
                left = right;
            } else
            // 如果 right 位置能赢，接下来它至少会赢一次
            {
                int count = right - left;
                if (count >= k) {
                    return right;
                }
                left++;
            }
        }

        return maxIndex;
    }
}

2.双指针解法（代码已优化）

class Solution {
    public int findWinningPlayer(int[] skills, int k) {
        int n = skills.length;
        int maxPlayer = n-1; // 临时记录最大 skill 的 player 位置
        int maxSkill = skills[maxPlayer];
        int left = 0; // 定义 left 指针
        while (left<n-1){
            if (skills[left]>maxSkill){
                maxPlayer = left;
                maxSkill = skills[left];
            }
            int right = left+1; // 定义 right 指针
            while (right<n && skills[right]<skills[left]){
                right++;
            }
            int count = left==0?right-left-1:right-left;
            if (count>=k){
                return left;
            }
            left = right;
        }
        return maxPlayer;
    }
}

上面有一个小细节，在获得 maxPlayer 的时候，实际上是进行的不充分比较，并没有比较所有的 skill[i]，但是剩余那部分没有使用到的 skill 一定是相对较小的，不用比较他们也没有关系。