數(shù)據(jù)結(jié)構(gòu)解決滑動(dòng)窗口問(wèn)題

前文用 [單調(diào)棧解決三道算法問(wèn)題]介紹了單調(diào)棧這種特殊數(shù)據(jù)結(jié)構(gòu)，本文寫(xiě)一個(gè)類似的數(shù)據(jù)結(jié)構(gòu)「單調(diào)隊(duì)列」。

也許這種數(shù)據(jù)結(jié)構(gòu)的名字你沒(méi)聽(tīng)過(guò)，其實(shí)沒(méi)啥難的，就是一個(gè)「隊(duì)列」，只是使用了一點(diǎn)巧妙的方法，使得 隊(duì)列中的元素全都是單調(diào)遞增（或遞減）的 。

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

比如說(shuō)力扣第 239 題「滑動(dòng)窗口最大值」，難度 Hard ：

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

函數(shù)簽名如下：

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

比如說(shuō)題目給出的一個(gè)示例：

一、搭建解題框架

這道題不復(fù)雜，難點(diǎn)在于如何在O(1)時(shí)間算出每個(gè)「窗口」中的最大值，使得整個(gè)算法在線性時(shí)間完成。這種問(wèn)題的一個(gè)特殊點(diǎn)在于，「窗口」是不斷滑動(dòng)的，也就是你得動(dòng)態(tài)地計(jì)算窗口中的最大值。

對(duì)于這種動(dòng)態(tài)的場(chǎng)景，很容易得到一個(gè)結(jié)論：

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

回到這道題的場(chǎng)景，每個(gè)窗口前進(jìn)的時(shí)候，要添加一個(gè)數(shù)同時(shí)減少一個(gè)數(shù)，所以想在 O(1) 的時(shí)間得出新的最值，不是那么容易的，需要「單調(diào)隊(duì)列」這種特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)輔助。

一個(gè)普通的隊(duì)列一定有這兩個(gè)操作：

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

一個(gè)「單調(diào)隊(duì)列」的操作也差不多：

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

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

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

這個(gè)思路很簡(jiǎn)單，能理解吧？下面我們開(kāi)始重頭戲，單調(diào)隊(duì)列的實(shí)現(xiàn)。

二、實(shí)現(xiàn)單調(diào)隊(duì)列數(shù)據(jù)結(jié)構(gòu)

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

「單調(diào)隊(duì)列」的核心思路和「單調(diào)棧」類似，push方法依然在隊(duì)尾添加元素，但是要把前面比自己小的元素都刪掉：

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ù)字的大小代表人的體重，把前面體重不足的都?jí)罕饬?，直到遇到更大的量?jí)才停住。

如果每個(gè)元素被加入時(shí)都這樣操作，最終單調(diào)隊(duì)列中的元素大小就會(huì)保持一個(gè)單調(diào)遞減的順序，因此我們的max方法可以可以這樣寫(xiě)：

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

pop方法在隊(duì)頭刪除元素n，也很好寫(xiě)：

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

之所以要判斷data.front() == n，是因?yàn)槲覀兿雱h除的隊(duì)頭元素n可能已經(jīng)被「壓扁」了，可能已經(jīng)不存在了，所以這時(shí)候就不用刪除了：

至此，單調(diào)隊(duì)列設(shè)計(jì)完畢，看下完整的解題代碼：

/* 單調(diào)隊(duì)列的實(shí)現(xiàn) */
class MonotonicQueue {
    LinkedList

有一點(diǎn)細(xì)節(jié)問(wèn)題不要忽略，在實(shí)現(xiàn)MonotonicQueue時(shí)，我們使用了 Java 的LinkedList，因?yàn)殒湵斫Y(jié)構(gòu)支持在頭部和尾部快速增刪元素；而在解法代碼中的res則使用的ArrayList結(jié)構(gòu)，因?yàn)楹罄m(xù)會(huì)按照索引取元素，所以數(shù)組結(jié)構(gòu)更合適。

三、算法復(fù)雜度分析

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

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

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

其實(shí)我覺(jué)得，這種特殊數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)還是蠻有意思的，你學(xué)會(huì)單調(diào)隊(duì)列的使用了嗎？學(xué)會(huì)了給個(gè)三連？