3 單調隊列與單調棧

課程內容#

問題引入#

$RMQ (x, y)$ 函數：查詢數組 $[x, y]$ 區間內部的最小值，參考RMQ——OI Wiki
如果固定詢問區間的尾部，例如：$RMQ (x,7)$
- 最少記錄如下 4 個藍色元素，即可滿足 $RMQ (x,7)$ 的所有需求
- 並且這 4 個元素構成了一個單調遞增的序列，也是單調隊列
單調隊列解決的就是這類維護區間最值的問題 [固定結尾的 RMQ 問題]

單調隊列#

要解決的問題性質：維護滑動窗口內部的區間最值
結構定義：單調的隊列
結構操作
- 入隊：先將隊尾違反單調性的元素淘汰出局，再將當前元素入隊
- 出隊：如果隊首元素超出了滑動窗口的範圍，隊首出隊
維護的核心：隊首元素—— 滑動窗口內的最值⭐
- 最小值→遞增隊列
- 最大值→遞減隊列
均攤時間複雜度：O (1)，求解一次
[PS] 再舉個例加深印象：學校選出學生代表去參賽
- 類比：年級 -> 數組索引，能力值 -> 數據值，時間段 -> 滑動窗口
- 在維護區間 [14-17] 最大值的單調隊列中，當你入隊時，趙六就會被踢出
  - 延伸：如果一個人年齡比你小，能力還比你強，那你就永遠被踢掉了

單調棧#

想想棧和隊列的區別，而單調棧和單調隊列的唯一区別也就在這，其它操作一致 [入隊、出隊]
- 單調棧是一頭堵死的單調隊列
- 單調棧保留了單調隊列的入隊操作，依然維護單調性⭐
問題性質：最近（大於 / 小於）關係
- 入棧之前，符合單調性的棧頂元素，就是當前入棧元素的最近（大於 / 小於）關係
維護的核心：棧頂元素—— 最近（大於 / 小於）關係⭐
- 左側最近關係→左側先入棧
- 右側最近關係→右側先入棧
- [PS] 其棧底是全局最小值，但用棧維護並沒有意義
均攤時間複雜度：O (1)，求解一次

兩者對比#

其實兩者主要是形式上不同，但本質差不多

| |開放端口|維護核心|擅長問題|基本操作|
|:----:|:----|:----:|:----|:----:|:----|:----:|:----|:----|
|單調隊列| 首、尾 | 隊首 | 區間最值 | 維單 + 入隊、出隊、取值|
|單調棧| 頂 | 棧頂 | 最近大小關係 | 出棧 [維單]、取值、入棧 |

隨堂練習#

—— 引入 ——#

HZOJ-261：數據結構#

樣例輸入

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

樣例輸出

2
3

思路
- 數據規模：$1\le N\le 1000$
- 【關鍵】類比終端的光標操作，維護光標所在的位置⭐
- 【數據結構】對頂棧，兩個棧 s1、s2 的棧頂對應光標位置 [也可用數組或鏈表模擬]
- 【操作分析】
  - 插入：s1 入棧某元素
  - 刪除：s1 出棧
  - 左移：s1 棧頂元素轉移到 s2
  - 右移：s2 棧頂元素轉移到 s1
  - 查詢：維護一個前綴和數組 sum 以及最大前綴和數組 ans，ans 中存的就是答案
- [PS] 如果用單純一個數組實現，插入很耗時
代碼
- 新造一個數據結構 -> 結構定義 + 結構操作
  - 定義好數據結構後，可以很方便地使用其方法
- 維護前綴數組 sum 和與最大前綴和數組 ans 的時機
  - 在向 s1 插入元素時：插入操作、右移操作
  - 刪除操作、左移操作本也需維護，但 HZOJ 的測試樣例存在BUG：查詢時的 k 值，在大於光標當前位置 [即 s1.size ()] 時，答案仍考慮 1~k 的最大前綴和，所以需要保留 s2 中每個位置對應的最大前綴和
- [PS]
  - sum、ans 數組第 0 位需要保留一個初始值，用於初始的前綴和累加和比較
  - ans 的數據只負責比較，不負責運算；sum 的數據只負責運算，不負責比較
  - 查詢操作輸入的 k 可能比總長度大，所以也可以特判一下，返回整體的最大前綴和

HZOJ-263：火車進棧#

樣例輸入

樣例輸出

思路
- 注意題幹：1~n 按順序進站；輸出前 20 種答案
- 首先思考樣例輸出中，會有 312 嗎？
  - 如果想要第一個得到 3，需要壓入 1、2，那麼出棧只能是 321
- 【關鍵】判斷全排列中的序列是否合法
- 假設，已經進棧的最大列車編號，為 $x$；全排列的一個序列中當前待出棧的的數字是 $y$
  - 如果 $y ≤ x$，說明 $y$ 必須是棧頂元素，否則序列不合法
  - 如果 $y > x$，先將 $[x + 1,\ y]$ 中的所有元素入棧，此時棧頂元素一定是 y
  - 舉例：判斷 4132、3241 是否合法？
    - 注意 $x$、$y$ 的比較，$x$ 只會增或者不變，不會減
    - 可自行模擬一遍
代碼
- 注意棧中棧頂指針和當前入棧的最大值的巧妙利用 [棧用數組模擬]
- top == -1 的判斷是為了通用性，在這裡不會存在
- 利用函數bool next_permutation(begin, end)得到下一組排列 [按字典序升序的]，返回值代表是否有下一組排列
  - 參考cplusplus

—— 單調隊列 ——#

HZOJ-271：滑動窗口#

樣例輸入

8 3
1 3 -1 -3 5 3 6 7

樣例輸出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路
- 數據規模：$1\le N \le 300000$
- 純單調隊列，關注代碼實現
代碼
- 思考：單調隊列中是記錄值還是記錄【下標】
  - 記錄下標🆒，因為有了下標可以索引到值 [順藤摸瓜]
  - 記錄值，卻反向不可查
- 這是一個常用的單調隊列模板：維護單調性→入隊→出隊→根據題意輸出
- 關注最大 / 小值、窗口的大小
- [PS] 隊尾既可以入隊，也可以出 [踢，維護單調性]，所以認為不是單向隊列

HZOJ-372：雙生序列#

樣例輸入

5
3 1 5 2 4
5 2 4 3 1

樣例輸出

思路
- 思考：什麼是兩個序列的趨勢相同？
  - 相同區間內部的 RMQ 值相同，❗ 這裡 RMQ 值→最小值的最大下標
- 【關鍵】兩個序列的每個區間的 RMQ 值相等👉兩個序列的單調隊列長得一樣
  - 換句話說，每時每刻，兩個序列對應相同的單調隊列
  - 注意：長得一樣，指的不是最小值，而是對應下標 [單調隊列裡存的是下標]
- 將兩個序列的元素，依次插入到單調隊列中，每次插入後比較單調隊列的大小即可
  - ① 如果一致，繼續入隊
  - ② 如果不一致，輸出答案
代碼
- 用類定義單調隊列，便於復用
- 單調隊列裡存的是下標：p
- 單調隊列操作：維護→入隊，都不需要出隊
- 【巧妙】根據隊列的大小變化把握趨勢變化

HZOJ-270：最大子序和#

樣例輸入

6 4
1 -3 5 1 -2 3

樣例輸出

思路
- 子序和 → 區間和，利用前綴和可得
- 限定條件：子序列的長度不超過 $m$→ 滑動窗口
- 因此，轉換為前綴和數組上的問題
  - 目標：$max_j {s_i-s_j}\ |\ 0\lt i-j\le m$，即找最小的 $s_j$，得到 $max_j {Sum_{j+1}^i}$
    - $s_i$ 代表原序列前 $i$ 個元素的和
- 【問題轉換】
  - 在前綴和數組$s$ 上，維護一個大小為 $m$ 的滑動窗口的最小值
- 👉 單調隊列。注意：維護的不是原序列，而是前綴和數組
代碼
- 單調隊列操作：出隊→取值→維護單調性 + 入隊
  - 本來套路是先維護單調性 + 入隊，即，出隊和取值操作放在後面 [這樣是沒問題的]
  - 但調換了順序也可以：因為窗口大小 $m\ge1$，所以隊列中至少最後一個元素用不到，所以取值放在前面也不會漏值
  - [PS] 出隊操作只要在取值前即可
- 只需要前綴和信息，原信息不用建立數組
- ❗ 對於求區間和，不要忘記前綴和數組 0 號元素的意義，單調隊列初始記得壓入它

—— 單調棧 ——#

HZOJ-264：最大矩形面積#

樣例輸入

7
2 1 4 5 1 3 3

樣例輸出

思路
- 思考：最大矩形的性質 ——> 矩形高度 = 所在區域最矮的木板高度 x
  - 如果矩形高度 > x，不能構成矩形
  - 如果矩形高度 < x，為什麼不能 = x 呢？
- 具體思路
  - 反過來，確定以某一塊木板作為當前矩形的高度，向左向右找第一個比它小的高度，中間的面積就是其能得到的最大矩形面積
  - 再遍歷每一塊木板求得的最大面積，取最大值
- 需要求解：每一塊木板最近的高度小於當前木板的位置，所以使用【單調棧】
- [啟發] 分析最優解的性質，是解決問題的第一步
代碼
- 需要數組存儲的數據有：木板高度數據、單調遞增棧、存儲左 / 右最近最小
- 要注意邊界的處理技巧：兩端設置高度極小的木板 [-1]，同時初始化好棧底，為高度極小的木板的索引 [0、n + 1]
- 最後將左 / 右整合到一起，計算面積，取最大即可
- 這也是一個常用的單調棧模板：維護單調性 [出棧] →根據題意取值→入棧
- 樣例解析：
  - 注意單調棧裡存儲的是索引值

Tips#

結合單調隊列 / 棧的動態規劃問題請跳轉：2 從遞推到動態規劃（下）