力扣每日一题3185. 构成整天的下标对数目 II

看到数据范围n是1e5, k是1e9就可以知道，这题目暴力模拟肯定会超时。

但我们看，在k比n大情况下，一轮循环下来肯定是没有赢家的，需要多轮。当然，我们肯定不可能去一轮一轮模拟，那我们怎么判断谁是赢家呢？其实在这种情况下，有固定的一个人一定是赢家，这个人应该会是谁呢？答案当然是技能值最高的啊。稍微想一想应该很容易想到原因。因为不可能有人击败他，那么只要他开始比赛，后面就一定是他连续赢下去，直到比赛结束。

我们假定技能值最高的人的编号是x。根据前面的分析，我们可以知道，如果其他玩家想要能连续赢k场，那这个玩家的所有比赛一定是在遇到这位x之前就赢了k场比赛了。

这样，我们要模拟的比赛就从k场变成了遇到x之前的所有比赛了。那么，这些比赛我们真的需要把赢得放到第一个，输了的放到最后一个这样去模拟吗？如果你要把最前面的数字移到最后面，还保持其他数据的顺序不变，那只能一个个的把元素往前挪，时间复杂度O(n)，在最坏情况下，你需要将n个数都这样移动，时间复杂度O(n^2)。又是超时。

不能模拟，那怎么办呢？实际上我们可以直接一次循环查找它能不能连续赢k场，因为如果它输了一次比赛，那它就被移到了队伍末尾，已经在x之后了，在它下一次出场之前，x已经先出场了。只有x出场，那最后胜出的就只会是x。

因此，我们可以从前到后去遍历玩家 i，判断它能否连续赢下 k 次（其实就是判断它后面的k个数都比它小）。如果能，就直接返回答案 i，不能就继续遍历，直到遇到x就可以结束遍历了。

不过有一个小细节需要注意一下。如果当前的 i 不为 0，那么第 i 个玩家最少已经赢了一次，因为与 i 进行比赛的上一个玩家，已经输掉比赛排到了末尾。

思路已经确定了，剩下的代码就很好写了。就遍历数组记录一下当前的玩家 i 和它赢的次数就可以了。

class Solution {
public:int findWinningPlayer(vector<int>& skills, int k) {int n=skills.size();int maxs=skills[0], maxi=0;for (int i=1; i<n; i++){if (skills[i] > maxs){maxs = skills[i];maxi = i;}}if (k > n){return maxi;}int now=0, cnt=0, win=0;for (int i=1; i<maxi; i++){if (skills[now] > skills[i]){cnt++;if (cnt >= k){win = 1;break;}}else // skills[now] < skills[i]{now = i;cnt=1;if (cnt >= k){win = 1;break;}}}if (win == 1){return now;}else return maxi;}
};

只有两个for循环进行遍历，时间复杂度O(n),空间复杂度O(1)。

其实这个代码还可以再优化一下。直接一次循环找连续赢k场的玩家的同时记录下最大值就可以了。而且这个最大值就是循环结束的时候排在第一个的那个人，都不需要额外用变量去记录了。