找出数组游戏的赢家
难度:
标签:
题目描述
给你一个由 不同 整数组成的整数数组 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^51 <= arr[i] <= 10^6arr所含的整数 各不相同 。1 <= k <= 10^9
代码结果
运行时间: 44 ms, 内存: 26.6 MB
import java.util.*;
import java.util.stream.*;
/**
* This class contains a method to find the winner of a game using Java Streams.
* The method iterates over the array comparing the first two elements, keeps the larger
* element at the front and moves the smaller element to the end. It keeps track of the
* consecutive wins of the current front element, and when it reaches k, returns that element
* as the winner.
*/
public class GameWinnerStream {
public static int getWinner(int[] arr, int k) {
Deque<Integer> deque = new ArrayDeque<>();
Arrays.stream(arr).forEach(deque::offer);
int currentWinner = deque.poll();
int winCount = 0;
while (winCount < k) {
int challenger = deque.poll();
if (challenger > currentWinner) {
deque.offer(currentWinner);
currentWinner = challenger;
winCount = 1;
} else {
deque.offer(challenger);
winCount++;
}
}
return currentWinner;
}
public static void main(String[] args) {
int[] arr1 = {2, 1, 3, 5, 4, 6, 7};
int k1 = 2;
System.out.println(getWinner(arr1, k1)); // Output: 5
int[] arr2 = {3, 2, 1};
int k2 = 10;
System.out.println(getWinner(arr2, k2)); // Output: 3
int[] arr3 = {1, 9, 8, 2, 3, 7, 6, 4, 5};
int k3 = 7;
System.out.println(getWinner(arr3, k3)); // Output: 9
int[] arr4 = {1, 11, 22, 33, 44, 55, 66, 77, 88, 99};
int k4 = 1000000000;
System.out.println(getWinner(arr4, k4)); // Output: 99
}
}
解释
方法:
此题解采用模拟比赛的方式进行。首先，检查k是否大于等于数组长度减一，如果是，直接返回数组中的最大值，因为最大的元素一定能够在足够多的回合中连续获胜。否则，使用变量cur来记录当前连胜的数字，tmp来记录当前数字还需要赢得多少回合才能成为赢家。遍历数组中的元素，如果cur大于当前元素，则cur的连胜次数(tmp)减一；如果小于，更新cur为当前元素，并重置tmp为k-1。如果tmp降到0，则当前cur为赢家，直接返回。如果遍历结束后没有找到赢家，则返回最后的cur，因为它已经是剩下的最大值。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中，你是如何确定当k大于等于数组长度减一时，返回数组中的最大值就是最优解的？
▷🦆
为什么选择使用两个变量cur和tmp来追踪当前赢家和剩余胜利次数？有没有可能用其他数据结构来优化这个过程？
▷🦆
在循环中，当当前元素cur大于数组中的下一个元素时，为什么tmp需要减1？这是否意味着每次比较都默认cur已经赢得了一局？
▷🦆
如果在某一次比较中，新的元素比cur大，tmp被重置为k-1。这种做法是否考虑了之前cur赢得的所有比赛？
▷