一、單調棧

1、使用場景

解決元素左 / 右側第一個比他大 / 小的數字。

2、原理解釋

用棧解決，目標是棧頂存儲答案。

以元素左側第一個比他小為例：

（1）遍歷順序一定是從左向右。

（2）由于棧頂一定是答案，所以如果棧頂比遍歷到的元素大或相等，那就是不合法的，此時一直出棧。?

（3）一直到棧空或棧頂比元素小，分別表示元素左邊沒有數比元素小和元素左邊有數比元素小。更新答案。

（4）此時不管怎么樣都把元素入棧，因為這個元素可能會是之后的答案。

3、代碼

例題：單調棧

P5788 【模板】單調棧 - 洛谷

// https://www.luogu.com.cn/problem/P5788
#include "bits/stdc++.h"
using namespace std;
// 找到右邊大的數
// 除非我遍歷到的這個數比頂大我才一直出棧（循環解決），棧為空那就是右邊沒有比我大的我入棧，棧不為空那說說明右邊有比我大的我入棧
const int N = 1e7;
int a[N];
int ans[N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];stack<int> st;for(int i = n; i >= 1; i--){while(st.size() && a[st.top()] <= a[i])st.pop();if(st.empty()){st.push(i);ans[i] = 0;}else {ans[i] = st.top();st.push(i);}}for(int i = 1; i <= n; i++){cout << ans[i] << ' ';}return 0;
}

4、例題

發射站

P1901 發射站 - 洛谷

// https://www.luogu.com.cn/problem/P1901
#include "bits/stdc++.h"
using namespace std;
#define ll long long
// 兩個數組：
// 左邊離塔最近的高于這個塔的下標
// 右邊離塔最近的高于這個塔的下標
// 兩個棧分別找到
// 加能量應該是左邊比塔高的那個塔加這個塔的能量，top += i
const int N = 1e6 + 10;int sum[N]; // 對應下標的塔接受的能量
int v[N]; // 塔的高度
int e[N]; // 塔的能量
int ans = 0;
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)cin >> v[i] >> e[i];stack<int> st1;stack<int> st2;for(int i = 1; i <= n; i++){while(st1.size() && v[i] >= v[st1.top()])st1.pop();if(st1.size()){sum[st1.top()] += e[i];}st1.push(i);}for(int i = n; i >= 1; i--){while(st2.size() && v[i] >= v[st2.top()])st2.pop();if(st2.size()){sum[st2.top()] += e[i];}st2.push(i);}for(int i = 1; i <= n; i++){ans = max(ans, sum[i]);}cout << ans;return 0;
}

二、單調隊列

1、使用場景

滑動窗口極值問題。

2、原理解釋

用隊列，目標是隊頭是答案。

以滑動窗口中的極大值為例：

（1）因為隊頭是窗口中的最大值，所以一個元素要入隊尾插那一定是盡可能向前走，即比元素小的或相等的（剛進來的元素不容易被淘汰，所以相等的老東西也要走）全部尾刪。

（2）最后隊為空或者尾刪停下后，更新尾插。

（3）解決完入隊邏輯之后還要解決數據過期，即不在窗口內的元素要清除，所以在每次插入新元素之后對于下標過期的數據循環頭刪。

3、代碼

例題：單調隊列

P1886 滑動窗口 /【模板】單調隊列 - 洛谷

// https://www.luogu.com.cn/problem/P1886
#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 10;
int a[N];
// 雙端隊列，存下標防止數據過期
// 最小值：隊為空直接加，來的數比隊尾大不一定就不是后面的答案尾插，來的數比隊尾小或等于可以競爭這個范圍內的最小值，所以一直尾刪。每次最后清除所有不合法下標。
// 最大值：隊為空直接加，來的數比隊尾小不一定就不是后面的答案尾插，來的數比隊尾大或等于可以競爭這個范圍內的最大值，所以一直尾刪。每次最后清除所有不合法下標。
int main()
{int n, k;deque<int> dq1;deque<int> dq2;cin >> n >> k;for(int i = 1; i <= n; i++)cin >> a[i];// 最小for(int i = 1; i <= n; i++){while(dq1.size() && a[i] <= a[dq1.back()]) dq1.pop_back();dq1.push_back(i);while(dq1.front() <= i - k)dq1.pop_front();if(i >= k)cout << a[dq1.front()] << ' ';}cout << endl;// 最大for(int i = 1; i <= n; i++){while(dq2.size() && a[i] >= a[dq2.back()]) dq2.pop_back();dq2.push_back(i);while(dq2.front() <= i - k)dq2.pop_front();if(i >= k)cout << a[dq2.front()] << ' ';}return 0;
}

4、例題

1、質量檢測

P2251 質量檢測 - 洛谷

// https://www.luogu.com.cn/problem/P2251
#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main()
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];deque<int> dq;for(int i = 1; i <= n; i++){while(dq.size() && a[i] <= a[dq.back()])dq.pop_back();dq.push_back(i);while(dq.front() <= i - m)dq.pop_front();if(i >= m)cout << a[dq.front()] << endl;}return 0;
}

2、HISTOGRA - Largest Rectangle in a Histogram

SP1805 HISTOGRA - Largest Rectangle in a Histogram - 洛谷

// https://www.luogu.com.cn/problem/SP1805
#include <iostream>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL h[N];
LL x[N], y[N];
int main()
{
while(cin >> n, n)
{
for(int i = 1; i <= n; i++) cin >> h[i];
// 找左邊，?
stack<int> st;
for(int i = 1; i <= n; i++)
{
// 單調遞增的棧 - 存下標
while(st.size() && h[st.top()] >= h[i]) st.pop();
if(st.size()) x[i] = st.top();
else x[i] = 0;
st.push(i);
}
// 找右邊，?
while(st.size()) st.pop();
for(int i = n; i >= 1; i--)
{while(st.size() && h[st.top()] >= h[i]) st.pop();
if(st.size()) y[i] = st.top();
else y[i] = n + 1;
st.push(i);
}
LL ret = 0;
for(int i = 1; i <= n; i++)
{
ret = max(ret, h[i] * (y[i] - x[i] - 1));
}
cout << ret << endl;
}
return 0;
}