【题目】 给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。 每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。 返回赢得比赛的整数。 题目数据 保证 游戏存在赢家。 【示例】 > 输入：arr = [2,1,3,5,4,6,7], k = 2 > 输出：5 > 解释：一起看一下本场游戏每回合的情况： > 因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。 --- 【我的思路】 模拟过程，如果k大于等于arr的长度，则说明arr中最大的那个数就是赢家（因为最大的那个数会一直赢），否则就模拟比较过程，如果arr[0] > arr[1]，则arr[0]的连胜次数+1，将arr[1]添加到arr的末尾，arr删除arr[1]，注意如果arr[0] <= arr[1]，那么arr[0]的连胜次数要清零，并将arr[0]添加到arr的末尾，arr删除arr[0]，且arr[1]的连胜次数要置为1，然后继续比较，直到连胜次数达到k，返回arr[0]。 【我的代码】 ```c++ class Solution { public: int getWinner(vector& arr, int k) { int win = 0; //记录连胜次数 if(k >= arr.size()) return *max_element(arr.begin(), arr.end()); //如果k大于等于arr的长度，则返回arr中最大的那个数 else{ while(win < k){ if(arr[0] > arr[1]){ win ++; //如果arr[0]大于arr[1]，则arr[0]连胜次数+1 int temp = arr[1]; //保存arr[1]的值 arr.erase(arr.begin() + 1); //删除arr[1] arr.push_back(temp); //将arr[1]添加到末尾 } else{ win = 1; //如果arr[0]小于等于arr[1]，则arr[0]连胜次数清零，并将arr[0]添加到末尾，删除arr[0] int temp = arr[0]; //保存arr[0]的值 arr.erase(arr.begin()); //删除arr[0] arr.push_back(temp); //将arr[0]添加到末尾 } } } return arr[0]; } }; ``` 但是上面的代码在k过大时，可能会超时，例如： ```c++ arr = [1, 2, 3] k = 10 ``` 因此上面的代码可以进一步优化，思路如下： 如果k大于等于arr的长度，则直接返回arr中的最大值，因为数组中最大的那个数会一直赢； 否则，我们模拟整个比较过程，使用一个变量cur表示当前的擂主，win表示当前连胜的次数，我们从数组的第一个元素开始，依次与后面的元素进行比较： 如果cur大于后面的元素，则win++，表示当前擂主获胜，继续与后面的元素比较； 如果cur小于等于后面的元素，则cur更新为后面这个元素，win重置为1，表示当前擂主被击败，新的擂主开始比赛； 当win达到k时，返回cur，即为赢家。 代码如下： ```c++ class Solution { public: int getWinner(vector& arr, int k) { int cur = arr[0]; //当前擂主 int win = 0; //连胜次数 if(k >= arr.size()) return *max_element(arr.begin(), arr.end()); //如果k大于等于arr的长度，返回数组中的最大值 else{ for(int i = 1; i < arr.size(); ++i){ //从第二个元素开始遍历 if(cur > arr[i]){ //如果当前擂主大于后面的元素，则连胜次数+1 win ++; } else{ //如果当前擂主小于等于后面的元素 cur = arr[i]; //更新擂主为后面的元素 win = 1; //重置连胜次数 } if(win == k) return cur; //如果连胜次数达到k，则返回当前擂主 } } return cur; //遍历完成后返回当前擂主 } }; ```
