前言

昨天聊了單調堆疊，單調堆疊解決了下一個最大/最小元素的問題，那麼如果我們把佇列也套上單調性，能夠解決什麼樣的問題嗎？
在陣列的部分，我們聊過滑動窗口的問題，滑動窗口主要是透過操作左右指針，來維護左右指針中夾著的區間，因該區間具特別的意義。
但假設我們現在要求區間元素中的最大值，搭配窗口不停滑動，那我們是不是就得不斷的遍歷區間，才能夠比對出區間的最大值呢？
這樣的問題叫做「滑動窗口最大值」，也是單調佇列主要能夠解決的問題。

單調佇列的構成

單調佇列一如昨天單調性定義的能讓儲存空間裡的元素依序遞增或遞減，昨天操作的是堆疊，今天做的是佇列。
因為並沒有這個類別，讓我們先來實現這個類別 ─ 我們假設是個遞減佇列(第一個元素為最大)。
我們預期會有三個方法

void Push(int) : 放入元素到佇列尾端
void Pop(int) : 佇列在回傳最大值的區間中移除該元素
int Max() : 回傳佇列中最大的元素，時間複雜度預計為 O(1)

實現上的概念其實和單調佇列相近，為了維持一致性，當我們放入元素時，必須保證放入的元素小於尾端元素，而如果比尾端元素大，則應該把尾端元素彈出，再把元素放進去。
因為這個佇列的存在是解決給定區間的最大值的問題(Max())，那些被彈出的元素已經不可能成為最大值(在這個區間內被加入了更大的元素)才被彈出，所以我們並不關心這些元素是誰，只關心可能成為最大值的元素。
而 Pop 的操作是說要在給定區間中移除特定元素，我們只注意特定元素是否為當前佇列的最大值，否則並不影響 Max() 的結果，我們也就不處理。只有彈出的元素的正好是當前佇列的最大值時，則我們就把該元素從佇列的最前頭移除，順理成章地、下一個數就會是最大值。
任何時候，想要知道這個佇列裡的最大值，只要訪問佇列頭即可。

以上描述的實現，有一個地方跟一般的佇列結構比較不一樣，他會需要能夠知道和移除尾端的元素，所以實現單調佇列時不好直接用內建的佇列來做。取而代之，C# 中有個結構 LinkedList(雙向鏈結串列)，具有相關的函式，我們下面使用這個類別來建構單調佇列。

public class MonotonicQueue{
    private LinkedList<int> queue;
    public MonotonicQueue(){
        queue = new LinkedList<int>();
    }
    public void Push(int val){
        while(queue.Count > 0 && queue.Last.Value < val){
            queue.RemoveLast();
        }
        queue.AddLast(val);
    }
    public int Max(){
        return queue.First.Value;
    }
    public void Pop(int val){
        if(queue.First.Value == val){
            queue.RemoveFirst();
        }
    }
}

就如上面描述的方式去實現，我們得到了能夠在 O(1) 時間內回傳我們給定區間最大值的類別。

Sliding Window Maximum

在今天前言的地方已經介紹了這個題目，在窗口不停滑動的情況下，回傳每個窗口當下的最大值。
窗口大小為 k，如果每次透過遍歷來得到窗口的最大值，則時間複雜度為 O(k)，加上陣列長度 n，則總時間複雜度為 O(n*k)。
但是套用上面的單調佇列，讓我們以 O(1) 的代價拿到區間最大值，則我們就能把時間複雜度降為 O(n)。

起初我們先建構上面定義好的單調佇列。
以 i 為 index 遍歷陣列，接著先將窗口長度 k 的元素塞滿單調佇列，在塞滿的這一刻才開始做窗口空除。
空除的就是第 k - i + 1 個元素，呼叫單調佇列的 Pop(num[k - i + 1])。
最後持續在佇列塞滿的情況下呼叫 Max，並放入答案陣列中。
遍歷完成陣列時，回傳答案陣列。

public int[] MaxSlidingWindow(int[] nums, int k) {
    var monotonicQueue = new MonotonicQueue();//參考上方定義
    var result = new int[nums.Length - k + 1];
    for(var i = 0; i < nums.Length; i++){
        monotonicQueue.Push(nums[i]);
        if(i < k-1){
            continue;
        }
        result[i - k + 1] = monotonicQueue.Max();
        monotonicQueue.Pop(nums[i-k+1]);
    }
    return result;
}

這邊可能會想，為什麼是裝到第 k 個元素就要做排除？那是因為，如果不排除，則下次裝入時，窗口就有總共 k+1 個元素，這是不合理的，也就沒辦法回傳正確的結果。所以每次迴圈完，取完最大值後，佇列中最多應該是 k - 1 個元素，讓下次 push 進去，取最大值時，佇列正好是 k 個元素。

單調佇列的優點就是善於處理變動區間的最大值，當給定區間長度，要持續的利用小的時間成本獲取區間中的最大最小值，單調佇列就會是優先的選項。