題目連結:
題目意譯:
給定一個相異整數陣列 arr 以及一個整數 k。
接著,有一個遊戲將進行於該陣列的前兩個元素之上(即 arr[0] 和 arr[1])。在遊戲的每一回合中,我們將比較 arr[0] 和 arr[1] 兩者之值,較大的數字將會贏下該回合並留在位置 0,而較小者將會被移動至陣列的結尾。此遊戲在某個整數贏下連續 k 回合後結束。
回傳最後贏得遊戲的整數。
保證這些遊戲必定有最後的贏家。
限制:
2 ≦ arr.length ≦ 10 ^ 5
1 ≦ arr[i] ≦ 10 ^ 6
arr 包含著相異整數。
1 ≦ k ≦ 10 ^ 9
範例測資:
範例 1:
輸入: arr = [2,1,3,5,4,6,7], k = 2
輸出: 5
解釋: 讓我們看看遊戲中的每一回合:
回合 | arr | 贏家 | 連續贏數
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
所以我們可以看到遊戲將進行 4 個回合,而 5 將會是最後的贏家,因為它贏了連續 2 回合。
範例 2:
輸入: arr = [3,2,1], k = 10
輸出: 3
解釋: 3 將會贏得連續的前 10 回合。
解題思維:
首先,我們可以看到如果 k 大於等於 arr.length - 1,則最後的贏家必定是 arr 中數字最大者(因為此時只有它才能連續贏至少 k 次)。
接著對於剩下的 k 值之情況,我們直接模擬即可。
而要模擬這個過程,我們可以使用雙端佇列(Deque)來實作——即每次我們從該佇列的前面取出兩個元素,比較完後將大的放前面、小的放後面即可。不直接使用陣列是因為你會需要把某個元素移動到最尾端並將剩餘元素遞補「空隙」(這樣會很慢)。
而這樣子的模擬過程最糟頂多就是找到 arr 中的最大值之後再做 k 次比較,因此時間複雜度會是 O(arr.length + k)。再加上我們已經把 k ≧ arr.length - 1 的情況先行判斷掉了,因此「這邊」的時間複雜度可以直接寫為 O(arr.length)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。