淺談單調隊列

本篇随筆簡單講解一下算法競賽中的一種資料結構—單調隊列。

與淺談單調棧是姐妹篇，同樣需要前置知識...你得知道隊列是啥，然後單調這個詞啥意思。

一、單調隊列的概念

單調隊列。

就是前置知識加和。

單調+隊列。

也就是說，對于這個單調隊列來講，隊列中的元素是滿足單調性的。

那麼當然有單調遞增隊列和單調遞減隊列等等的分類。

這就是單調隊列了。

需要注意的一點是，這與普通的隊列小有不同，普通隊列要從尾入，從頭出。但單調隊列由于要維護單調性，需要從尾入，從頭從尾都能出。也就是，如果要用C++STL的話，要用deque。

二、單調隊列的應用

單調隊列的概念非常簡單，那麼它的精髓就在于應用，也就是在隊列上加了個單調性，它能夠支援解決的問題有什麼變化。

單調隊列所維護的問題是動态區間最大、最小值。也就是我們熟悉的“滑動視窗”。

當然，因為不帶修，可以考慮用樹狀數組、線段樹、ST表等各種log算法水。但是資料範圍稍大一些，不用\(O(N)\)算法想過這道題，就是癡心妄想。

動态區間最大最小值維護的精髓就是：直接取隊首元素，就是答案。那麼為了維護這個隊首元素最大/最小，我們要采取如下的維護政策：首先，對于新加入元素，如果不符合單調性質，就從隊尾彈到符合為止，如果符合性質直接入隊。但是由于像滑動視窗等題目還會有其他限制，比如不能讓超出範圍的最小值繼續成為最小值。那麼這個時候要在隊列中同時維護這個限制，然後從隊首出隊。

三、單調隊列優化DP

這是單獨的一個部分。我們會開單獨的部落格進行講解：

淺談單調隊列優化DP