Leetcode-1535. Find the winner of the array game

link

1535. Find the winner of the array game

subject

Here you are Different An array of integers arr And an integer k .

Each round of the game is in the first two elements of the array （ namely arr[0] and arr[1] ） Carry out between . Compare arr[0] And arr[1] Size , A larger number will win the round and remain in place 0 , The smaller integers are moved to the end of the array . When an integer wins k For consecutive rounds , Game over , This integer is the match's Winner .

Returns the whole number that won the game .

Subject data Guarantee There are winners in the game .

Example

 

Example 1：
Input ：arr = [2,1,3,5,4,6,7], k = 2
Output ：5
explain ： Let's take a look at each round of the game ：
So there will be 4 Round match , among 5 It's a winner , Because it won in a row 2 round .

Example 2：
Input ：arr = [3,2,1], k = 10
Output ：3
explain ：3 Will be in front of 10 Win in a row in a round .

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

explain

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr  The integer contained in   Each are not identical  .
• 1 <= k <= 10^9

Ideas

You only need to traverse once , And there is no need to change the array .

• 1. Suppose the first element is the current winner , Compare it with the following elements .
• 2. If the first element is larger （ Win. ）, Then the number of victories +1, until k Time , Returns the winner's value .
• 3. If the first element is smaller （ lost , And it hasn't arrived yet k）, Then change the current larger element to the winner , Recycle the above process , until k Time , Or the array has been traversed .

Already compared k The end of this time is very easy to understand , So why can the array end directly after traversal ？ At this time, there is no comparison k Time , It has not been compared with the elements in front of the array , This is because we already have the answer , The current largest element must be larger than all the previous elements , Because it is eliminated all the way from the previous elements , Up to him .

C++ Code

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int winner=arr[0]; // The current winner 
        int wintime=0; // The number of times the current winner wins 
        for(int i=1;i<arr.size()&&wintime<k;i++)
        {
            if(winner>arr[i]) wintime++;
            else
            {
                winner=arr[i];
                wintime=1;
            }
        }
        return winner;
    }
};