1535. 找出数组游戏的赢家——medium

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况：
因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

示例 2：
**
输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

示例 3：
**
输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

示例 4：
**
输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99

提示：

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr 所含的整数 各不相同 。
• 1 <= k <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-winner-of-an-array-game

思路:
首先很容易想到模拟方法：按照题面意思，每次比较后，对数组进行修改，这个方法时间复杂度为O(n)。这个复杂度肯定是不能接受的，能否不修改数组，直接扫描一遍数组就得到答案呢？可以。

• 定义变量prev 表示当前第一的数字，这样就只需循环的时候和prev进行比较大小，不需要移动修改数组。第一轮比赛时prev = Math.max(arr[0],arr[1])，这里有一个边缘case：当k等于1时，此时已经获得了答案，返回prev即可
• 如果当前第一已经胜利了k轮，则讲结果返回。如果扫描完数组以后，仍没有数字连胜k轮呢？那么答案必定会是数组中最大的数字，在之后的比赛中一定能连胜k轮。

复杂度分析：
时间复杂度O(n)
空间复杂度O(1)

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var getWinner = function(arr, k) {
    let prev  = Math.max(arr[0],arr[1]);
    if(k === 1) return prev;
    let win = 1;
    let winner = prev;
    for(let i = 2;i < arr.length;i++){
        if(prev > arr[i]){
            win += 1;
            if(win === k) {
                return prev;
            }
        }else{
            prev = arr[i];
            win = 1;
        }
        winner = Math.max(winner,arr[i])
    }
    return winner
};