單調隊列 和 單調棧

單調隊列

定義

有一個隊列(雙端隊列)， 隊列中的元素滿足下面四種狀态的任何一種都為單調隊列:

• 單調遞增 (如 1 2 3 5 9)
• 單調不減 (如 1 2 3 3 5)
• 單調遞減 (如 9 5 3 2 1)
• 單調不增 (如 5 3 3 2 1)

性質

 (以單增隊列為例)

 插入時，需要将尾部大于此數的全部出隊。

 删除時，根據需要使隊首或者隊尾的元素出隊(是以要用雙端隊列)。

 每時每刻隊首元素都代表着目前區間範圍内的最小值。

 單調隊列維護元素值的同時也要維護元素的下标，以便知道每個元素和整個區間的關系。

實作

int q[maxn], p[maxn], ft, rr;
for(int i = ; i <= n; ++i) {
    while(rr > ft && q[rr-1] >= a[i]) --rr;
    q[rr++] = a[i], p[rr-] = i;
    //if(p[ft]<k) ++ft;
}
           

應用

 個人對單調隊列有以下幾點感覺：

 單調隊列多用于區間問題，而且大多數是區間長度或者其他的有限制的問題。

 單調隊列的研究對象一般是某個元素，而非某個區間(個人感覺)， 個人感覺要維護的基本上是某個元素的一些相關屬性。

 有幾個題目作為例子:

POJ - 2823 Sliding Window: 滑動視窗 單調隊列

HDU - 3415 Max Sum of Max-K-sub-sequence : 單調隊列

HDU - 3530 Subsequence : 單調隊列

 另外單調隊列還有一個大用處就是優化一種形式的dp, 由于我還沒有研究到dp，這裡就先放一放，列一下知識點和一個題目感受一下。

(以下言論來自百度百科， 不可全信)

做動态規劃時常常會見到形如這樣的轉移方程：

f[x] = max or min { g(k) | b[x] <= k < x } + w[x]

其中b[x]随x單調不降，即b[1]<=b[2]<=b[3]<=…<=b[n]

(g[k]表示一個和k或f[k]有關的函數，w[x]表示一個和x有關的函數)

 這個方程怎樣求解呢？我們注意到這樣一個性質：如果存在兩個數j, k，使得j <= k，而且g(k) <= g(j)，則決策j是毫無用處的。因為根據b[x]單調的特性，如果j可以作為合法決策，那麼k一定可以作為合法決策，并且k是一個比j要優的決策。因為k比j要優，（注意：在這個經典模型中，“優”是絕對的，是與目前正在計算的狀态無關的），是以，如果把待決策表中的決策按照k排序的話，則g(k)必然是不降的。在此例中決策表即f[x].

這樣，就引導我們使用一個單調隊列來維護決策表。對于每一個狀态f(x)來說，計算過程分為以下幾步：

1、 隊首元素出隊，直到隊首元素在給定的範圍中。

2、 此時，隊首元素就是狀态f(x)的最優決策，

3、 計算g(x)，并将其插入到單調隊列的尾部，同時維持隊列的單調性（不斷地出隊，直到隊列單調為止）。

 重複上述步驟直到所有的函數值均被計算出來。不難看出這樣的算法均攤時間複雜度是O(1)的。是以求解f(x)的時間複雜度從O(n^2)降到了O(n)。

 單調隊列指一個隊列中的所有的數符合單調性（單調增或單調減），在資訊學競賽的一些題目上應用，會減少時間複雜度.

 可以參考下面這道題了解

POJ - 3017 Cut the Sequence : 單調隊列優化dp

單調棧

定義

 個人感覺這個棧和隊列是差不多的，其實單調棧隻要在單調隊列的基礎上，關掉隊列的一個端點不就行了， 隻能在一端操作就是棧了，是以在實際的編碼中單調棧和單調隊列是差不多的(還是個人感覺)。

性質

 同單調隊列

實作

 同單調隊列

應用

目前我做到的四道題都隻是用來求一個問題的:

就是在一個數組中， 求一個元素和它向左向右不比它小的元素所能組成的最大的區間，就是它最遠能擴充到的地方，這應該是單調棧最簡單的應用了(還沒做到難的)。

HDU - 1506 Largest Rectangle in a Histogram: 單調棧入門題

另外還有三道題和這題差不多，我這裡給出題目連結， 讀者可作為練習實驗下。

POJ - 3250 Bad Hair Day

POJ - 2796 Feel Good (這題是此書上的習題)

HDU - 1505 City Game