一、單調(diào)棧

所謂單調(diào)棧，就是指滿足單調(diào)性的棧結(jié)構(gòu)：

• 單調(diào)遞增棧： 棧中元素從棧底到棧頂是遞增的；
• 單調(diào)遞減棧： 棧中元素從棧底到棧頂是遞減的。

例如對于單調(diào)遞增棧，向其中插入元素的時候，為了維護(hù)棧的單調(diào)性，需要在保證將該元素插入到棧頂后整個棧滿足單調(diào)性的前提下彈出最少的元素：

stack<int> stk;void insert(int x) {while (!stk.empty() && stk.top() > x)  // 當(dāng)stk.top() <= x時滿足單調(diào)性stk.pop();stk.push(x);
}

單調(diào)?？梢杂脕碓谝粋€數(shù)組中尋找某一個元素左邊（或右邊）第一個大于（或小于或大于等于或小于等于）它的元素（或元素的下標(biāo)）。

這句話看起來有些繞，接下來我們只考慮以下四種「基本情形」。

情形一：尋找一個數(shù)左邊第一個小于它的數(shù)

給定一個長度為 $n(\le 10^5)$ 的數(shù)組 $a$，輸出每個數(shù)左邊第一個比它小的數(shù)，如果不存在則輸出 $?1$。

傳統(tǒng)的暴力做法是雙重循環(huán)：

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int a[N];int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) {bool flag = false;for (int j = i - 1; ~j; j--) {if (a[j] < a[i]) {flag = true;cout << a[j] << ' ';break;}}if (!flag) cout << -1 << ' ';}return 0;
}

然而這種做法的復(fù)雜度是 $O(n^2)$，利用單調(diào)棧，我們可以將復(fù)雜度降低至 $O(n)$。

在指針 $i$ 從左往右遍歷的過程中，我們可以用一個棧來保存 $i$ 左邊的所有元素（不包括 $i$ 指向的元素），下標(biāo)越大的元素越接近棧頂，下標(biāo)越小的元素越接近棧底。

每次我們訪問棧頂，只要棧頂元素大于等于 $a[i]$，我們就將棧頂元素彈出，直至棧頂元素小于 $a[i]$，此時輸出棧頂元素并將 $a[i]$ 壓入棧中。 由于棧中保存了 $i$ 左邊的所有元素，所以只要有答案，則答案一定在棧中。

📃 對證明不感興趣的讀者可以跳過這部分
講到這里，可能會有讀者好奇，棧不是一直在彈出元素嗎，萬一先前就把答案彈出去了怎么辦？這里我們可以從數(shù)學(xué)的角度進(jìn)行證明。假設(shè)對于 $a[i]$，答案一定存在，即

$$?0\le p<i,\text{s.t.}\{\begin{array}{l}a[p]<a[i],\\ a[t]>a[p],t=p+1,?,i?1\end{array}$$

對于第二個約束，假設(shè)有某個 $a[t]\le a[p]$，那么可知 $a[t]<a[i]$ 并且 $a[t]$ 在 $a[p]$ 的右邊，從而 $a[t]$ 才應(yīng)該是答案，矛盾！

下面證明，當(dāng)指針指向 $a[i]$ 時，$a[p]$ 一定存在于棧中。
當(dāng)指針指向 $a[p]$ 時，這一輪循環(huán)結(jié)束后，$a[p]$ 會被壓入棧中，所以我們從 $p+1$ 開始考慮。事實上，$?t\in [p+1,i?1]$，當(dāng)指針指向 $a[t]$ 時，無論棧怎么彈出元素，都不會彈出 $a[p]$，這是因為棧彈出元素的前提是棧頂元素 $\ge a[t]$，而 $a[p]<a[t]$ 所以不會被彈出，自然地，當(dāng)指針指向 $a[i]$ 時，$a[p]$ 仍在棧中。

由于每個元素一定會被壓入一次且至多彈出一次，因此操作次數(shù)至多是 $2n$，故總時間復(fù)雜度為 $O(n)$。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int a[N], ans[N];stack<int> stk;int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) {while (!stk.empty() && stk.top() >= a[i]) stk.pop();if (!stk.empty()) ans[i] = stk.top();else ans[i] = -1;stk.push(a[i]);}for (int i = 0; i < n; i++) cout << ans[i] << ' ';return 0;
}

📝 代碼完全可以簡化，之所以這么寫是為了方便統(tǒng)一格式。

情形二：尋找一個數(shù)左邊第一個小于它的數(shù)的下標(biāo)

和情形一類似，只不過這里我們尋找的是下標(biāo)，如果不存在則輸出 $?1$。

只需對棧做一點小小的修改就能應(yīng)對情形二。注意到之前我們尋找的是元素所以讓棧去保存元素，現(xiàn)在我們尋找下標(biāo)，所以讓棧去保存元素的下標(biāo)就可以了。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int a[N], ans[N];stack<int> stk;int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) {while (!stk.empty() && a[stk.top()] >= a[i]) stk.pop();  // 僅有兩處修改if (!stk.empty()) ans[i] = stk.top();else ans[i] = -1;stk.push(i);  // 僅有兩處修改}for (int i = 0; i < n; i++) cout << ans[i] << ' ';return 0;
}

情形三：尋找一個數(shù)右邊第一個大于它的數(shù)

之前我們是在一個數(shù)的左邊去尋找，所以讓棧去保存這個數(shù)左邊的所有數(shù)，類似地，現(xiàn)在需要讓棧去保存這個數(shù)右邊的所有數(shù)。

考慮將數(shù)組翻轉(zhuǎn)（實際上不可能翻轉(zhuǎn)，而是倒序遍歷），因此情形三變成了「尋找一個數(shù)左邊第一個大于它的數(shù)」，于是歸結(jié)為情形一。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int a[N], ans[N];stack<int> stk;int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = n - 1; ~i; i--) {while (!stk.empty() && stk.top() <= a[i]) stk.pop();if (!stk.empty()) ans[i] = stk.top();else ans[i] = -1;stk.push(a[i]);}for (int i = 0; i < n; i++) cout << ans[i] << ' ';return 0;
}

情形四：尋找一個數(shù)右邊第一個大于它的數(shù)的下標(biāo)

結(jié)合情形二和情形三即可得出。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int a[N], ans[N];stack<int> stk;int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = n - 1; ~i; i--) {while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();if (!stk.empty()) ans[i] = stk.top();else ans[i] = -1;stk.push(i);}for (int i = 0; i < n; i++) cout << ans[i] << ' ';return 0;
}

不難發(fā)現(xiàn)，這四種情形只在第 $16,17,20$ 行不同，其余部分的代碼均相同，據(jù)此可以總結(jié)出以下三點區(qū)別：

• 遍歷順序（以怎樣的順序遍歷數(shù)組 $a$）；
• 比較方式（如何比較當(dāng)前元素和棧頂元素）；
• 棧中存儲的是什么（是元素本身還是元素的下標(biāo)還是其他）。

二、單調(diào)棧的應(yīng)用

2.1 單調(diào)棧模板題I

原題鏈接：AcWing 830. 單調(diào)棧

此題對應(yīng)情形一，不再贅述，直接給出AC代碼。

#include <bits/stdc++.h>using namespace std;stack<int> stk;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;while (n--) {int x;cin >> x;while (!stk.empty() && stk.top() >= x) stk.pop();if (!stk.empty()) cout << stk.top() << ' ';else cout << -1 << ' ';stk.push(x);}return 0;
}

2.2 單調(diào)棧模板題II

原題鏈接：洛谷 P5788 【模板】單調(diào)棧

此題對應(yīng)情形四，不再贅述，直接給出AC代碼。

#include <bits/stdc++.h>using namespace std;const int N = 3e6 + 10;int a[N], ans[N];
stack<int> stk;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = n; i; i--) {while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();if (!stk.empty()) ans[i] = stk.top();stk.push(i);}for (int i = 1; i <= n; i++) cout << ans[i] << ' ';return 0;
}

2.3 Bad Hair Day

原題鏈接：POJ 3250 Bad Hair Day

本題類似于情形四，但還是有些區(qū)別。

首先應(yīng)當(dāng)注意到以下幾點：

• 每頭牛只向右看；
• 每頭牛只能看見比自己低的牛的頭頂；
• 若兩頭牛一樣高，則它們互相看不到對方的頭頂。

這相當(dāng)于對數(shù)組中的某個數(shù)，我們要在它的右邊尋找第一個大于等于它的數(shù)的下標(biāo)，知道下標(biāo)后，我們就可以算出這頭牛能夠看到多少頭牛的頭頂了。當(dāng)然，如果找不到這樣的數(shù)，說明這頭牛的右邊全是比它低的牛，此時用牛的數(shù)量減去該牛的下標(biāo)（從 $1$ 開始）就是該牛能夠看到的頭頂?shù)臄?shù)量。

還需注意一個問題，假設(shè)給定的序列是單調(diào)遞減的，那么所求答案為 $N(N?1)/2\approx 3\times 10^9$，會爆 int。

#include <stack>using namespace std;typedef long long LL;LL h[80010], ans;
stack<LL> stk;int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);for (int i = n; i; i--) {while (!stk.empty() && h[stk.top()] < h[i]) stk.pop();if (!stk.empty()) ans += stk.top() - i - 1;else ans += n - i;stk.push(i);}printf("%lld", ans);return 0;
}

三、單調(diào)隊列

單調(diào)隊列的定義類似于單調(diào)棧：

• 單調(diào)遞增隊列： 從隊尾到隊頭單調(diào)遞增；
• 單調(diào)遞減隊列： 從隊尾到隊頭單調(diào)遞減。

例如對于單調(diào)遞增隊列，向其中插入元素的時候，為了維護(hù)隊列的單調(diào)性，需要在保證將該元素插入到隊尾后整個隊列滿足單調(diào)性的前提下彈出最少的元素（從隊尾彈出）：

deque<int> q;  // 因為涉及到從隊尾彈出，所以只能用雙端隊列來實現(xiàn)單調(diào)隊列void insert(int x) {while (!q.empty() && q.back() < x)q.pop_back();q.push_back(x);
}

?? 嚴(yán)格意義上講單調(diào)隊列并不是隊列，因為它不滿足FIFO。

四、單調(diào)隊列的應(yīng)用

4.1 滑動窗口

原題鏈接：AcWing 154. 滑動窗口

單調(diào)隊列常用于求滑動窗口中的最大（小）值。我們先來看一下這道題的暴力解法是什么樣的：

#include <bits/stdc++.h>using namespace std;typedef long long LL;const LL INF = 3e9;LL a[1000010];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i <= n - k; i++) {LL mini = INF;for (int j = i; j < i + k; j++) mini = min(mini, a[j]);cout << mini << ' ';}cout << "\n";for (int i = 0; i <= n - k; i++) {LL maxi = -INF;for (int j = i; j < i + k; j++) maxi = max(maxi, a[j]);cout << maxi << ' ';}return 0;
}

顯然時間復(fù)雜度為 $O(nk)$，基本會TLE。使用單調(diào)隊列，我們可以將時間復(fù)雜度降低至 $O(n)$。

以求最小值為例，我們使用單調(diào)遞減隊列來保存滑動窗口中的元素，下標(biāo)越大的元素越接近隊尾，下標(biāo)越小的元素越接近隊頭，于是求滑動窗口中的最小值相當(dāng)于訪問隊頭元素。

不妨設(shè)下標(biāo)從 $1$ 開始，初始時 $i$ 指向 $1$，并且 $i$ 從 $1$ 遍歷至 $n$，每次遍歷都將 $a[i]$ 插入到隊列中?？梢园l(fā)現(xiàn)，只要有 $i<k$ 就說明滑動窗口還未形成，此時無需輸出最小值，當(dāng) $i\ge k$ 時才需要輸出最小值。

那何時彈出隊頭元素呢？不妨讓單調(diào)隊列保存的是元素的下標(biāo)而非元素本身，設(shè)當(dāng)前窗口為 $a[i?k..i?1]$，向單調(diào)隊列插入 $i$ 后，新窗口變成 $a[i?k+\mathrm{1..}i]$，如果隊頭元素小于等于 $i?k$，說明最小值不在新窗口中，此時應(yīng)當(dāng)彈出隊頭元素。

到目前為止，可以總結(jié)出兩點：

• 只要 $i\ge k$ 就應(yīng)當(dāng)輸出隊頭元素；
• 當(dāng)隊頭元素小于等于 $i?k$ 時，彈出隊頭元素。

#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int a[N];
deque<int> q;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) {while (!q.empty() && a[q.back()] > a[i]) q.pop_back();q.push_back(i);if (!q.empty() && q.front() <= i - k) q.pop_front();  // 既可以用if也可以用whileif (i >= k) cout << a[q.front()] << ' ';}cout << "\n";q.clear();for (int i = 1; i <= n; i++) {while (!q.empty() && a[q.back()] < a[i]) q.pop_back();q.push_back(i);if (!q.empty() && q.front() <= i - k) q.pop_front();  // 既可以用if也可以用whileif (i >= k) cout << a[q.front()] << ' ';}return 0;
}

此題還可以用優(yōu)先隊列來做，為避免不必要的判斷，我們可以在一開始就向隊列中插入前 $k$ 個元素：

#include <bits/stdc++.h>using namespace std;typedef pair<int, int> PII;
const int N = 1e6 + 10;int a[N];
priority_queue<PII> p;  // 大根堆
priority_queue<PII, vector<PII>, greater<>> q;  // 小根堆int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= k; i++) q.emplace(a[i], i);cout << q.top().first << ' ';for (int i = k + 1; i <= n; i++) {q.emplace(a[i], i);while (!q.empty() && q.top().second <= i - k) q.pop();  // 只能用whilecout << q.top().first << ' ';}cout << "\n";for (int i = 1; i <= k; i++) p.emplace(a[i], i);cout << p.top().first << ' ';for (int i = k + 1; i <= n; i++) {p.emplace(a[i], i);while (!p.empty() && p.top().second <= i - k) p.pop();  // 只能用whilecout << p.top().first << ' ';}return 0;
}

觀察上面兩段代碼，可以發(fā)現(xiàn)思路是大致相同的，但區(qū)別在于（請看注釋行），單調(diào)隊列在彈出隊頭元素的時候既可以用 if 也可以用 while，而優(yōu)先隊列彈出隊頭元素的時候只能用 while，這是為什么呢？

考慮數(shù)組 $[4,6,2,3,5,1,8,7,9]$，窗口大小為 $3$，以求最小值為例，每次循環(huán)結(jié)束后單調(diào)隊列和優(yōu)先隊列的狀態(tài)列在下表中：

?? 列表的左端是隊頭，右端是隊尾。
?? 對于優(yōu)先隊列，只需看列表的第一個元素，其后元素的次序無關(guān)緊要。

滑動窗口	單調(diào)隊列	優(yōu)先隊列
$[4,6,2]$	$[2]$	$[2,4,6]$
$[6,2,3]$	$[2,3]$	$[2,4,6,3]$
$[2,3,5]$	$[2,3,5]$	$[2,4,6,3,5]$
$[3,5,1]$	$[1]$	$[1,2,4,6,3,5]$
$[5,1,8]$	$[1,8]$	$[1,2,4,6,3,5,8]$
$[1,8,7]$	$[1,7]$	$[1,2,4,6,3,5,8,7]$
$[8,7,9]$	$[7,9]$	$[7,8,9]$

因為優(yōu)先隊列在插入元素的過程中不會彈出元素，所以只要隊頭位于窗口內(nèi)，那么優(yōu)先隊列的大小只增不減，這就導(dǎo)致優(yōu)先隊列中存在許多冗余元素（不屬于窗口內(nèi)的元素）。而單調(diào)隊列為了保持單調(diào)性，插入元素的時候會從隊尾彈出一些元素，這就保證了單調(diào)隊列中的元素始終是滑動窗口中的元素的子集，因此單調(diào)隊列的 while 循環(huán)至多執(zhí)行一次，自然可以改成 if。