1535. Find the Winner of an Array Game
给你一个阵列 arr 表示比赛顺序
k 表示胜利次数
每次比赛的时候 arr[0] 会跟 arr[1] 比
胜利的数字会跑到 arr[0] 而输的会跑到阵列尾端
游戏会进行到有人连续胜利 k 次后结束
例题:
1.
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
回合 | 阵列 | 胜者 | 胜利次数
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
5 连续胜利两次 比赛结束
2.
Input: arr = [3,2,1], k = 10
Output: 3
First think:
范例题目就展示了这一提的一个特性：
阵列中的最大值不一定是赢家
可能还没比完就找到赢家了
以一开始觉得阵列顺序可能会乱掉
如果会比到第二轮的话
需要对阵列做操作才能知道正确的比赛顺序
Approach:
仔细思考就能发现
如果第一轮比完的话
当下的卫冕者就是阵列最大值
所以接下来不管怎么比结果都不会变
这样的话我们就不需要考虑第二轮的状况
也就不需要进行阵列操作
单纯记录胜利次数就好了
TS code:
function getWinner (arr: number[], k: number): number {
let winner = arr[0]
let winCount = 0
const WinnerWin = () => {
winCount++
}
const WinnerLost = (newWinner: number) => {
winner = newWinner
winCount = 1
}
for (let i = 1; i < arr.length; i++) {
if (winner > arr[i]) {
WinnerWin()
} else {
WinnerLost(arr[i])
}
if (winCount === k) return winner
}
return winner
}