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.
Constraints:
2 <= arr.length <= 105
1 <= arr[i] <= 106
arr contains distinct integers.
1 <= k <= 109
按符号重排数组。
给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
思路是模拟。这里有两个 corner case 需要处理，如果 input 数组只有两个数字，那么赢家就是这两个值中间较大的那一个。另一个 case 是如果遍历一次之后，整个数组中未出现赢得 k 次游戏的数字，那么全局最大的数字是赢家，因为这个数字有可能排在 input 数组很后面的位置导致 index 比他大的数字的个数不足 k 个。
一般的情况是，我们比较了头两个元素之后，从第三个元素开始，就只和第一个元素（赢家）比较并记录连续赢得比赛的回合数，如果有任何一个数字连续赢得比赛的回合数 == k 则返回这个数字。
时间O(n)
空间O(n)
Java实现
class Solution {
public int getWinner(int[] arr, int k) {
int prev = Math.max(arr[0], arr[1]);
int count = 1;
int max = prev;
// corner case
if (k == 1) {
return prev;
}
// normal case
for (int i = 2; i < arr.length; i++) {
int cur = arr[i];
if (prev > cur) {
count++;
} else {
prev = cur;
count = 1;
}
if (count == k) {
return prev;
}
max = Math.max(max, arr[i]);
}
return max;
}
}