239. Sliding Window Maximum

給定一個陣列 nums 和 window size k ，每次 window 都會往右移一格，請找出每次移動 window 後最大的元素。

一開始只有想出很簡單的暴力解，我只紀錄最大元素的索引，如果當 window 內有更大的元素時，或是索引已經不在 window 內就要更新索引。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int max_index=0;
        for(int i=0; i<k; i++){
            if(nums[max_index] <= nums[i]){
                max_index = i;
            }
        }
        vector<int> result;
        result.push_back(nums[max_index]);

        for(int i=k; i<nums.size(); i++){
            
            if(max_index >= i && max_index <= i-k){
                //cout << "IF " << i << endl;
                if(nums[max_index] < nums[i]){
                    max_index = i;
                }
            }
            else{
                int temp_max_i = i;
                //cout << "ELSE " << i << endl;
                for(size_t j=i; j>i-k; j--){
                    if(nums[j] >= nums[temp_max_i]){
                        temp_max_i = j;
                    }
                }
                max_index = temp_max_i;
            }
            result.push_back(nums[max_index]);
        }
        return result;
    }
};

Time Complexity: O(n*k)
Space Complexity: O(1)

不過這解法有很大一個缺陷，若當 k 很大甚至接近 n 時，時間複雜度會到 n² (例如 nums 裡面元素是降序的時候 )，丟到 leetcode 會發現 TLE，所以我們需要優化一下。

應該先思考要如何在 O(1) 的情況下可以更新當前最大元素。以 nums=[1,-1,4,3,5] , k = 2為例，假如現在 window=[3,5] ，我不需要在window內依序尋找最大元素，而是可以透過某個機制去維護 index 就知道下個最大元素是 5 ，因為 4 已經在範圍外的前面了。

也就是說需要一個維持降序的 array ，但我們不需要用到 priority queue ，因為我們可以透過把 ≤ nums[i] 的元素從後面 pop 出來，然後再把 nums[i] 放進去。再來後有一個問題要處理，如果 array 裡面元素不在 window 內呢？

其實上面的問題解決後，就簡單許多， array 裡面改存 index 就行了，如果不在 window 內就不斷地從前面 pop 出來即可。所以我們需要一個陣列結構可以同時從前面跟後面pop，也要可以從後面 push index ，而 dequeue 剛好可以滿足這些條件。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;
        for(int i=0; i<nums.size(); i++){
            while(!dq.empty() && dq.front() < i - k + 1)
                dq.pop_front();
                
            while(!dq.empty() && nums[dq.back()] <= nums[i]){
                dq.pop_back();
            }

            dq.push_back(i);
            if(i >= k - 1)
                result.push_back(nums[dq.front()]);
                
        }

        return result;
    }
};

Time Complexity: O(n)
Space Complexity: O(k)

雖然需要額外 O(k) 記憶體空間，但可以見到大幅度的降低時間複雜度了。