🔗 🟡 1535. Find the Winner of an Array Game 1433

tags: `Weekly Contest 200` `模擬(Simulation)`

題意

給定一個由不同整陣列成的整數陣列 $arr$ 和一個整數 $k$ 。

在每一輪遊戲中，比較陣列的前兩個元素（即 $arr[0]$ 和 $arr[1]$ ），較大的整數將獲勝並保留在位置 $0$ ，較小的整數將移至陣列的末尾。當一個整數連續獲勝 $k$ 輪時，遊戲結束。

返回將贏得遊戲的整數，給定的數據確保遊戲一定會有獲勝者。

思路：模擬(Simulation)

若完全依照題意模擬，則時間複雜度約為 $(n + k)$ ，當 $k >> n$ 時，會有較大的時間複雜度。不妨思考一下，到底有沒有必要模擬 $k$ 輪遊戲？

顯然是不用的，若一個整數贏了 $n-1$ 次，其一定是最大值，因此當 $k \geq n - 1$ 時，此時直接返回最大值即可。

故首先特判 $k \geq n - 1$ 的情況，若不是，則進行模擬遊戲，並在遊戲結束時返回贏家。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(1)$

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k >= n - 1: # if k >= n - 1, only max value can win k times
            return max(arr)
        cur = arr[0] # current max candidate
        win = 0 # current win count
        for i in range(1, n):
            if arr[i] > cur: # new candidate
                cur = arr[i]
                win = 0
            win += 1
            if win == k:
                break
        return cur

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int n = arr.size();
        if (k >= n - 1) return *max_element(arr.begin(), arr.end());
        int cur = arr[0], win = 0;
        for (int i = 1; i < n && win < k; i++) {
            if (arr[i] > cur) {
                cur = arr[i];
                win = 0;
            }
            win += 1;
        }
        return cur;
    }
};