Problem#
給你一個數字不重複的整數陣列 arr 和一個整數 k，每次比較陣列第一個(arr[0])與第二個元素(arr[1])的大小，贏的數字會在 index 0，輸的數字則移動到 arr 的最後，其他數字依序往前移動一格。當有個數字連續贏 k 場時比賽結束，回傳贏的數字。
測資限制#
- $2 \le \text{len(arr)} \le 10^5$
- $1 \le \text{arr[i]} \le 10^6$
- $1 \le k \le 10^9$
- 保證每場比賽一定會有贏者
想法#
- Naive: 直接模擬 $n$ 個數字去比賽，直到某個數字勝出 $k$ 次，且真的去模擬所有數字往左移動 $\rightarrow$ TLE $O(n^2k)$
- 因為每次比賽都是比較大的勝出，如果 $n >= k$ 則可以確定的是此時陣列第一個元素(
arr[0])一定會是陣列中最大的數字(也就是max(arr[0] ... arr[n-1]))，因為每次都是找最大的，所以陣列每個數字都比過賽的話，自然贏者就是最大的數字 $\rightarrow$ 依舊 TLE $O(n^2)$ (因為 $n$ 蠻大) - 每次模擬比賽可以不用真的模擬數字移動，透過觀察不難發現，數字是從左往右依序與當前最大的去比較，因此可以用 index $[2, n)$ 掃過陣列，去跟當前最大比賽，如果當前最大贏了，則勝場 +1；如果當前最大輸了，則最大換人，且勝場數重設回 1，如果勝場數 $>= k$ 時回傳當前最大數字。如果迴圈都掃完了，還沒有數字的勝場 $>= k$ 時，此時答案依舊是當前最大數字。
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$
心得#
這題比想像中的麻煩