題目網址：https://leetcode.cn/problems/sliding-window-maximum/

題意：給一整數 array nums, 有一個大小為 k 的 sliding window 從 nums 的最左側移動到最右側。你只能看到 sliding window 中的 k 個數字, 且 sliding window 每次只向右移一位, 返回 sliding window 中的最大值。

Solution：

想法：利用 deque。因為 window 移除元素後, 有可能會改變最大值, 故也要記錄最大值之外的值。

首先, 建立遞減 Queue（Monotonic Queue）, 把當前 window 中最大值的 index 放在 deque 的最前面。

  • nums[i] 加入前, 要先不斷地和 deque.back() 比較
    • 若 nums[i] > nums[deque.back()], 則 deque.pop_back()
    • 若 nums[i] ≤ nums[deque.back()], 則將 i 放入 deque 最後面
  • 若 window 的起始位置 ≥ deque.front(), 代表在下一輪 deque.front() 超出 window 所涵蓋的範圍, 故要 pop 掉

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> index;
        vector<int> res;

        for (int i = 0; i < nums.size(); ++i) {
            // nums[i] 加入前, 要先不斷地和 deque.back() 比較
            while (!index.empty() && nums[i] > nums[index.back()]) {
                index.pop_back();
            }
            index.emplace_back(i);

            // i - k + 1 為當前 window 的起始位置
            // 當 window 中有足夠元素, 則將最大值 push 到 res 中
            if (i - k + 1 >= 0) {
                res.emplace_back(nums[index.front()]);
            }

            // 當前 window 的起始位置, 若 ≥ index.front()
            // 則在下一輪時, index.front() 會被移除(因為超出 window)
            if (i - k + 1 >= index.front()) {
                index.pop_front();
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 每個元素最多被 push／pop 一次
  • space：$O(k)$ ➔ deque 的元素個數不超過 k