1535.Find the Winner of an Array Game

Tags: Medium Array

Links: https://leetcode.com/problems/find-the-winner-of-an-array-game/

---

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9

Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99

Constraints:

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr contains distinct integers.
• 1 <= k <= 10^9

---

解法一：模拟

一次比较之后总会有一个数添加到序列的末尾，那么实现这个过程可以有两种选择：队列或者链表。为了简单实现，选择普通的队列即可，当然也可以选择deque双端队列。注意到k的数据范围是1e9，说明肯定有办法缩小范围，一个序列最大的数连胜的次数是n - 1，所以当k >= n - 1的时候，直接返回数组的最大值即可。

这里我们用一个while循环来模拟整个过程，因为k < n - 1，可知数组内的最大值必然符合条件，即至少存在一个满足条件的数，所以有合理的退出条件，就不会造成死循环。让tmp模拟arr[0]，队列的首端元素模拟arr[1]，cnt用来统计连胜的次数。

考虑最坏的情况，假如前n - 1个数字都不符合连胜的要求，那么最后一个数肯定是最大的数字，并且前面的数字一定符合下面这种排列：每个[]内的第一个数字大于当前[]内的余下数字，下一个[]的第一个数字必然大于前一个[]内的第一个数字，这样才能实现连胜次数不合要求。

[] [] [] [] ... max_element

一个很自然的想法是会不会存在多次循环遍历数组，答案是不会的，因为数组中最大的元素是比赛终结者，到max_element这里必然得出结果，最坏的结果就是遍历数组两次，时间复杂度是$O(n)$，空间复杂度是$O(n)$。

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = arr.size();
        if (k >= n - 1) return *max_element(arr.begin(), arr.end());

        queue<int> q;
        for (int i = 1; i < n; ++i) q.push(arr[i]);

        int res = arr[0], tmp = arr[0];
        int cnt = 0;

        while (true) {
            if (tmp > q.front()) {
                q.push(q.front()); q.pop();
                ++cnt;
            }
            else {
                q.push(tmp);
                tmp = q.front(); q.pop();
                cnt = 1;
                res = tmp;
            }

            if (cnt >= k) break;
        }

        return res;
    }
};

解法二： 假如一个数字的连胜次数中断，那么意味着破坏这个连胜次数的数字肯定要大于其前面的数字，所以完全可以只遍历一遍数组。

如果还没有遍历到末尾就存在一个数字的连胜次数等于k，那么直接返回结果；如果到了末尾虽然没有数字连胜次数大于等于k，但是最后一个打破前面连胜次数的数字就必然是最终结果，因为可以想象，把前面的数字移动到末尾再去比较，肯定都会小于这个数字，根据解法一的分析知道必然存在一个结果，既然前面的数字都不满足，那么就只能是当前选择的这个数字了。

免去了用队列模拟，时间复杂度$O(n)$，空间复杂度$O(1)$。

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = arr.size();
        if (k >= n - 1) return *max_element(arr.begin(), arr.end());

        int cnt = 0, res = arr[0];
        for (int i = 0; i < n - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                ++cnt;
                arr[i + 1] = arr[i];
            }
            else {
                res = arr[i + 1];
                cnt = 1;
            }

            if (cnt >= k) break;
        }

        return res;
    }
};