讀完本文，你可以去力扣拿下如下題目：

239.滑動視窗最大值

-----------

前文講了一種特殊的資料結構「單調棧」monotonic stack，解決了一類問題「Next Greater Number」，本文寫一個類似的資料結構「單調佇列」。

也許這種資料結構的名字你沒聽過，其實沒啥難的，就是一個「佇列」，只是使用了一點巧妙的方法，使得佇列中的元素單調遞增（或遞減）。這個資料結構有什麼用？可以解決滑動視窗的一系列問題。

看一道 LeetCode 題目，難度 hard：

一、搭建解題框架

這道題不復雜，難點在於如何在 O(1) 時間算出每個「視窗」中的最大值，使得整個演算法線上性時間完成。在之前我們探討過類似的場景，得到一個結論：

在一堆數字中，已知最值，如果給這堆數新增一個數，那麼比較一下就可以很快算出最值；但如果減少一個數，就不一定能很快得到最值了，而要遍歷所有數重新找最值。

回到這道題的場景，每個視窗前進的時候，要新增一個數同時減少一個數，所以想在 O(1) 的時間得出新的最值，就需要「單調佇列」這種特殊的資料結構來輔助了。

一個普通的佇列一定有這兩個操作：

class Queue {    void push(int n);    // 或 enqueue，在隊尾加入元素 n    void pop();    // 或 dequeue，刪除隊頭元素}

一個「單調佇列」的操作也差不多：

class MonotonicQueue {    // 在隊尾新增元素 n    void push(int n);    // 返回當前佇列中的最大值    int max();    // 隊頭元素如果是 n，刪除它    void pop(int n);}

當然，這幾個 API 的實現方法肯定跟一般的 Queue 不一樣，不過我們暫且不管，而且認為這幾個操作的時間複雜度都是 O(1)，先把這道「滑動視窗」問題的解答框架搭出來：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {    MonotonicQueue window;    vector<int> res;    for (int i = 0; i < nums.size(); i++) {        if (i < k - 1) { //先把視窗的前 k - 1 填滿            window.push(nums[i]);        } else { // 視窗開始向前滑動            window.push(nums[i]);            res.push_back(window.max());            window.pop(nums[i - k + 1]);            // nums[i - k + 1] 就是視窗最後的元素        }    }    return res;}

這個思路很簡單，能理解吧？下面我們開始重頭戲，單調佇列的實現。

二、實現單調佇列資料結構

首先我們要認識另一種資料結構：deque，即雙端佇列。很簡單：

class deque {    // 在隊頭插入元素 n    void push_front(int n);    // 在隊尾插入元素 n    void push_back(int n);    // 在隊頭刪除元素    void pop_front();    // 在隊尾刪除元素    void pop_back();    // 返回隊頭元素    int front();    // 返回隊尾元素    int back();}

而且，這些操作的複雜度都是 O(1)。這其實不是啥稀奇的資料結構，用連結串列作為底層結構的話，很容易實現這些功能。

「單調佇列」的核心思路和「單調棧」類似。單調佇列的 push 方法依然在隊尾新增元素，但是要把前面比新元素小的元素都刪掉：

class MonotonicQueue {private:    deque<int> data;public:    void push(int n) {        while (!data.empty() && data.back() < n)             data.pop_back();        data.push_back(n);    }};

你可以想象，加入數字的大小代表人的體重，把前面體重不足的都壓扁了，直到遇到更大的量級才停住。

如果每個元素被加入時都這樣操作，最終單調佇列中的元素大小就會保持一個單調遞減的順序，因此我們的 max() API 可以可以這樣寫：

void pop(int n) {    if (!data.empty() && data.front() == n)        data.pop_front();}

之所以要判斷 data.front() == n，是因為我們想刪除的隊頭元素 n 可能已經被「壓扁」了，這時候就不用刪除了：

至此，單調佇列設計完畢，看下完整的解題程式碼：

class MonotonicQueue {private:    deque<int> data;public:    void push(int n) {        while (!data.empty() && data.back() < n)             data.pop_back();        data.push_back(n);    }        int max() { return data.front(); }        void pop(int n) {        if (!data.empty() && data.front() == n)            data.pop_front();    }};vector<int> maxSlidingWindow(vector<int>& nums, int k) {    MonotonicQueue window;    vector<int> res;    for (int i = 0; i < nums.size(); i++) {        if (i < k - 1) { //先填滿視窗的前 k - 1            window.push(nums[i]);        } else { // 視窗向前滑動            window.push(nums[i]);            res.push_back(window.max());            window.pop(nums[i - k + 1]);        }    }    return res;}

三、演算法複雜度分析

讀者可能疑惑，push 操作中含有 while 迴圈，時間複雜度不是 O(1) 呀，那麼本演算法的時間複雜度應該不是線性時間吧？

單獨看 push 操作的複雜度確實不是 O(1)，但是演算法整體的複雜度依然是 O(N) 線性時間。要這樣想，nums 中的每個元素最多被 push_back 和 pop_back 一次，沒有任何多餘操作，所以整體的複雜度還是 O(N)。

空間複雜度就很簡單了，就是視窗的大小 O(k)。

四、最後總結

有的讀者可能覺得「單調佇列」和「優先順序佇列」比較像，實際上差別很大的。

趕緊去拿下 LeetCode 第 239 道題吧～