239. 滑動窗口最大值

思路

滑動窗口在滑動的時候，r++代表加入數字，l++代表左側數字離開窗口。
這個過程當中，想要隨時得到滑動窗口的最大值跟最小值，以下例子以找最大值為例。

1. 在最大值 $\max$ 離開窗口時，我們要將替補的數字加進來。
2. 在窗口進新數字時，若比當前 $\max$ 大，就取代掉。
3. 如果 $\max$ 的下標是 $i$ ，替補時， $i$ 前面的下標都不需要考慮。
   我們需要保留替補的一些數字，這些替補的數字，下標肯定會在 $i$ 後面。

我們用雙端隊列mx_q紀錄替補的數字，且mx_q的第一個數字，就是當前的最大值。 在新數字進來時：

1. 先把窗口左端邊界以外的數字都丟掉。
2. 再讓新進數字清除不合適的數字。

• 新數字的位置最靠後，它會是最後「過期」的數字
• 如果它比最爛的替補數字mx_q.back()還要好， 那麼mx_q.back()永遠不會成為窗口最大值。

程式碼

1.雙端隊列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        k--; // 將 k 變成閉區間，方便計算
        deque<int> mx_q;
        vector<int> res;
        for(int i = 0; i < n; i++) {
            while(!mx_q.empty() && mx_q.front() < i - k) { // 移除下標小於當前窗口左端的數字。
                mx_q.pop_front();
            }
            // 新進數字 nums[i], 會是最後過期的數字
            // 假如它數值比最爛替補還要大，那麼最爛替補永遠不會成為窗口最大值
            while(!mx_q.empty() && nums[mx_q.back()] <= nums[i]) {
                mx_q.pop_back();
            }
            mx_q.push_back(i);
            if(i < k) {
                continue;
            }
            // 最大值必定存在，不需要判斷是否為空
            res.push_back(nums[mx_q.front()]); 
        }
        return res;
    }
};

2. 數組模擬雙端隊列

class Solution {
private:
    static const int MX = 1e5+1;
    int mx_q[MX];
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int left = 0, right = 0; // 左閉右開
        int n = nums.size();
        k--; // 將 k 變成閉區間，方便計算
        vector<int> res;
        for(int i = 0; i < n; i++) {
            while(left != right && mx_q[left] < i - k) { // 移除下標小於當前窗口左端的數字。
                left++;
            }
            // 新進數字 nums[i], 會是最後過期的數字
            // 假如它數值比最爛替補還要大，那麼最爛替補永遠不會成為窗口最大值
            while(left != right && nums[mx_q[right - 1]] <= nums[i]) {
                right--;
            }
            mx_q[right++] = i;
            if(i < k) {
                continue;
            }
            // 最大值必定存在，不需要判斷是否為空
            res.push_back(nums[mx_q[left]]); 
        }
        return res;
    }
};

複雜度分析

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