數(shù)據(jù)結構解決滑動窗口問題

前文用 [單調棧解決三道算法問題]介紹了單調棧這種特殊數(shù)據(jù)結構，本文寫一個類似的數(shù)據(jù)結構「單調隊列」。

也許這種數(shù)據(jù)結構的名字你沒聽過，其實沒啥難的，就是一個「隊列」，只是使用了一點巧妙的方法，使得 隊列中的元素全都是單調遞增（或遞減）的 。

「單調?！怪饕鉀Q Next Great Number 一類算法問題，而「單調隊列」這個數(shù)據(jù)結構可以解決滑動窗口問題。我們之前的爆文 [滑動窗口解題套路框架]) 講的滑動窗口算法是雙指針技巧的一種，是解決子串、子數(shù)組的通用技巧；而本文說的滑動窗口是比較具體的問題。

比如說力扣第 239 題「滑動窗口最大值」，難度 Hard ：

給你輸入一個數(shù)組nums和一個正整數(shù)k，有一個大小為k的窗口在nums上從左至右滑動，請你輸出每次窗口中k個元素的最大值。

函數(shù)簽名如下：

int[] maxSlidingWindow(int[] nums, int k);

比如說題目給出的一個示例：

一、搭建解題框架

這道題不復雜，難點在于如何在O(1)時間算出每個「窗口」中的最大值，使得整個算法在線性時間完成。這種問題的一個特殊點在于，「窗口」是不斷滑動的，也就是你得動態(tài)地計算窗口中的最大值。

對于這種動態(tài)的場景，很容易得到一個結論：

在一堆數(shù)字中，已知最值為A，如果給這堆數(shù)添加一個數(shù)B，那么比較一下A和B就可以立即算出新的最值；但如果減少一個數(shù)，就不能直接得到最值了，因為如果減少的這個數(shù)恰好是A，就需要遍歷所有數(shù)重新找新的最值 。

回到這道題的場景，每個窗口前進的時候，要添加一個數(shù)同時減少一個數(shù)，所以想在 O(1) 的時間得出新的最值，不是那么容易的，需要「單調隊列」這種特殊的數(shù)據(jù)結構來輔助。

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

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

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

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

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

int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    List

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

二、實現(xiàn)單調隊列數(shù)據(jù)結構

觀察滑動窗口的過程就能發(fā)現(xiàn)，實現(xiàn)「單調隊列」必須使用一種數(shù)據(jù)結構支持在頭部和尾部進行插入和刪除，很明顯雙鏈表是滿足這個條件的。

「單調隊列」的核心思路和「單調?！诡愃?，push方法依然在隊尾添加元素，但是要把前面比自己小的元素都刪掉：

class MonotonicQueue {
    // 雙鏈表，支持頭部和尾部增刪元素
    private LinkedList<Integer> q = new LinkedList<>();

    public void push(int n) {
    // 將前面小于自己的元素都刪除
        while (!q.isEmpty() && q.getLast() < n) {
            q.pollLast();
        }
        q.addLast(n);
    }

}

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

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

public int max() {
    // 隊頭的元素肯定是最大的
    return q.getFirst();
}

pop方法在隊頭刪除元素n，也很好寫：

public void pop(int n) {
    if (n == q.getFirst()) {
        q.pollFirst();
    }
}

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

至此，單調隊列設計完畢，看下完整的解題代碼：

/* 單調隊列的實現(xiàn) */
class MonotonicQueue {
    LinkedList

有一點細節(jié)問題不要忽略，在實現(xiàn)MonotonicQueue時，我們使用了 Java 的LinkedList，因為鏈表結構支持在頭部和尾部快速增刪元素；而在解法代碼中的res則使用的ArrayList結構，因為后續(xù)會按照索引取元素，所以數(shù)組結構更合適。

三、算法復雜度分析

讀者可能疑惑，push操作中含有 while 循環(huán)，時間復雜度應該不是O(1)呀，那么本算法的時間復雜度應該不是線性時間吧？

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

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

其實我覺得，這種特殊數(shù)據(jù)結構的設計還是蠻有意思的，你學會單調隊列的使用了嗎？學會了給個三連？