目录
题目三——SP1805 HISTOGRA - Largest Rectangle in a Histogram - 洛谷
1.什么是单调栈？
单调栈（Monotone Stack）：其实就是一种特殊的栈，只不过在栈的「先进后出」规则基础上，要求「从 栈底 到 栈顶 的元素是单调递增（或者单调递减）」。其中
- 满足从栈底到栈顶的元素是单调递增的栈，叫做「单调递增栈」。
- 满足从栈底到栈顶的元素是单调递减的栈，叫做「单调递减栈」。
注意：这里定义的顺序是从「栈底」到「栈顶」。有的文章里是反过来的。本文全文以「栈底」到「栈顶」的顺序为基准来描述单调栈。
1.1.单调递增栈
单调递增栈：满足从栈底到栈顶的元素是单调递增的栈，叫做「单调递增栈」。
- 对于每一个试图进栈的元素A，都需要先将栈中>=A的元素先出栈，然后才可以将元素A入栈
- 这样就保证了：栈中保留的都是比当前入栈元素小的值，并且从栈底到栈顶的元素值是单调递增的。
单调递增栈的入栈过程，我们可以先看看用C++是怎么实现的！
const int N = 3e6 + 10; // 定义常量N，表示数组a的最大容量，这里设置为3,000,010
int a[N], n; // 定义全局数组a用于存储数据，n用于存储数据的数量
void test1()
{
stack<int> st; // 定义一个栈st，用于维护单调递增的元素
// 遍历数组a中的每个元素
for(int i = 1; i <= n; i++)
{
// 当栈不为空且栈顶元素大于等于当前元素a[i]时，将栈顶元素出栈
while(st.size() && st.top() >= a[i])
st.pop();
// 将当前元素a[i]压入栈中
st.push(a[i]);
}
}我知道单单看这个代码是有一点难懂的，所以我们看个例子。
下面我们以数组 [4,3,2,5,7,4,6,8]为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：
- 数组元素：[4,3,2,5,7,4,6,8]，遍历顺序为从左到右。
- 注意：栈底（左端），栈顶（右侧）
| 第 i 步 | 待插入元素 | 操 作 | 结 果（左侧为栈底） | 作用 |
|---|---|---|---|---|
| 1 | 4 | 4 入栈 | [4] | 元素 4 的左侧无比 4 小的元素 |
| 2 | 3 | 4 出栈，3 入栈 | [3] | 元素 3 的左侧无比 3 小的元素 |
| 3 | 2 | 3 出栈，2 入栈 | [2] | 元素 2 的左侧无比 2 小的元素 |
| 4 | 5 | 5 入栈 | [2, 5] | 元素 5 的左侧第一个比 5 小的元素是：2 |
| 5 | 7 | 7 入栈 | [2, 5, 7] | 元素 7 的左侧第一个比 7 小的元素是：5 |
| 6 | 4 | 7 出栈，5 出栈，4 入栈 | [2, 4] | 元素 4 的左侧第一个比 4 小的元素是：2 |
| 7 | 6 | 6 入栈 | [2, 4, 6] | 元素 6 的左侧第一个比 6 小的元素是：4 |
| 8 | 8 | 8 入栈 | [2, 4, 6, 8] | 元素 8 的左侧第一个比 8 小的元素是：6 |
最终栈中元素为 [2,4,6,8]。因为从栈底（左端）到栈顶（右侧）元素的顺序为 2,4,6,8，满足递减关系，所以这是一个单调递增栈。
我们以上述过程第 6 步为例，所对应的图示过程为：
1.2.单调递减栈
单调递增栈：满足从栈底到栈顶的元素是单调递减的栈，叫做「单调递减栈」。
- 对于每一个试图进栈的元素A，都需要先将栈中<=A的元素先出栈，然后才可以将元素A入栈
- 这样就保证了：栈中保留的都是比当前入栈元素大的值，并且从栈底到栈顶的元素值是单调递减的。
我们可以先看看代码是怎么写的
void test2()
{
stack<int> st; // 定义一个栈 st，用于维护单调递减的元素
// 遍历数组 a 中的每个元素
for(int i = 1; i <= n; i++)
{
// 当栈不为空且栈顶元素小于等于当前元素 a[i] 时，
while(st.size() && st.top() <= a[i])
st.pop();
// 将当前元素 a[i] 压入栈中。
st.push(a[i]);
}
}下面我们以数组 [2,7,5,4,6,3,4,2]为例，模拟一下「单调递增栈」的进栈、出栈过程。具体过程如下：
- 数组元素：[2,7,5,4,6,3,4,2]，遍历顺序为从左到右。
| 第 i 步 | 待插入元素 | 操 作 | 结 果（左侧为栈底） | 作 用 |
|---|---|---|---|---|
| 1 | 2 | 2 入栈 | [2] | 元素 2 的左侧无比 2 大的元素 |
| 2 | 7 | 2 出栈，7 入栈 | [7] | 元素 7 的左侧无比 7 大的元素 |
| 3 | 5 | 5 入栈 | [7, 5] | 元素 5 的左侧第一个比 5 大的元素为：7 |
| 4 | 4 | 4 入栈 | [7, 5, 4] | 元素 4 的左侧第一个比 4 大的元素为：5 |
| 5 | 6 | 4 出栈，5 出栈，6 入栈 | [7, 6] | 元素 6 的左侧第一个比 6 大的元素为：7 |
| 6 | 3 | 3 入栈 | [7, 6, 3] | 元素 3 的左侧第一个比 3 大的元素为：6 |
| 7 | 4 | 3 出栈，4 入栈 | [7, 6, 4] | 元素 4 的左侧第一个比 4 大的元素为：6 |
| 8 | 2 | 2 入栈 | [7, 6, 4, 2] | 元素 2 的左侧第一个比 2 大的元素为：4 |
最终栈中元素为 [7,6,4,2]。因为从栈底（左端）到栈顶（右侧）元素的顺序为 7,6,4,2，满足递减关系，所以这是一个单调递减栈。
我们以上述过程第 5 步为例，所对应的图示过程为：
2.单调栈适用场景
单调栈可以在时间复杂度为 O(n)的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。
所以单调栈一般用于解决一下几种问题：
- 寻找当前元素左侧第一个比当前元素大的元素。
- 寻找当前元素左侧第一个比当前元素小的元素。
- 寻找当前元素右侧第一个比当前元素大的元素。
- 寻找当前元素右侧第一个比当前元素小的元素。
虽然是四个问题，但是原理是⼀致的。因此，只要解决⼀个，举⼀反三就可以解决剩下的⼏个。
下面分别说一下这几种问题的求解方法。
2.1.寻找当前元素左侧第一个比当前元素大的元素
从左往右遍历元素，构造⼀个单调递减的栈。插⼊当前位置的元素的时：
如果栈为空，则左侧不存在⽐当前元素⼤的元素；
如果栈⾮空，插⼊当前位置元素时的栈顶元素就是所找的元素。
• 注意，因为我们要找的是最终结果的位置。因此，栈⾥⾯存的是每个元素的下标。
这个代码其实很好写的，我们只能从栈顶往栈底一个一个出栈，只要我们把栈顶的那些<=当前元素的，那出现的第一个栈顶元素是>当前元素的，那这个栈顶元素就一定是当前元素左侧第一个比当前元素大的元素了
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10; // 定义数组的最大长度
int a[N], n; // 数组a用于存储输入数据，n表示数组a中数据的数量
int ret[N]; // 结果数组
void test()
{
stack<int> st; // 定义一个栈st，用于维护一个单调递减的元素下标序列
for (int i = 1; i <= n; i++)
{
// 当栈不为空且栈顶元素对应的数组值小于等于当前元素a[i]时，
while (st.size() && a[st.top()] <= a[i])
st.pop();
// 如果栈不为空，说明存在比当前元素a[i]小的元素，栈顶元素就是所求结果。
if (st.size())
ret[i] = st.top();
// 将当前元素的下标i压入栈中。
st.push(i); // 注意这里存的是下标，而不是数组值。
}
for (int i = 1; i <= n; i++)
{
cout << ret[i] << " ";
}
cout << endl;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
test();
cout << endl;
}
2.2.寻找当前元素左侧第一个比当前元素小的元素
从左往右遍历元素，构造⼀个单调递增的栈。插⼊当前位置的元素的时：
如果栈为空，则左侧不存在⽐当前元素⼩的元素；
如果栈⾮空，插⼊当前位置元素时的栈顶元素就是所找的元素。
• 注意，因为我们要找的是最终结果的位置。因此，栈⾥⾯存的是每个元素的下标。
这个代码其实很好写的，我们只能从栈顶往栈底一个一个出栈，只要我们把栈顶的那些>=当前元素的，那出现的第一个<当前元素的就一定是当前元素左侧第一个比当前元素小的元素了
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N];
void test()
{
stack<int> st; // 定义一个栈st，用于维护一个单调递增的元素下标序列
for (int i = 1; i <= n; i++)
{
// 当栈不为空且栈顶元素对应的数组值大于等于当前元素a[i]时
while (st.size() && a[st.top()] >= a[i])
st.pop();
// 如果栈不为空，说明存在比当前元素a[i]小的元素，栈顶元素就是所求结果。
if (st.size())
ret[i] = st.top();
// 将当前元素的下标i压入栈中。
st.push(i); // 注意这里存的是下标，而不是数组值。
}
for (int i = 1; i <= n; i++)
{
cout << ret[i] << " ";
}
cout << endl;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
test();
cout << endl;
}
2.3.寻找当前元素右侧第一个比当前元素大的元素
针对其余两种情况，我们仅需逆序遍历数组即可。
从右往左遍历元素，构造⼀个单调递减的栈。插⼊当前位置的元素的时：
如果栈为空，则左侧不存在⽐当前元素⼤的元素；
如果栈⾮空，插⼊当前位置元素时的栈顶元素就是所找的元素。
• 注意，因为我们要找的是最终结果的位置。因此，栈⾥⾯存的是每个元素的下标。
注意我们的遍历顺序是从右边往左边了！！
这个代码其实很好写的，我们只能从栈顶往栈底一个一个出栈，只要我们把栈顶的那些<=当前元素的，那出现的第一个>当前元素的就一定是当前元素左侧第一个比当前元素大的元素了
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N];
void test()
{
stack<int> st;
for (int i = n; i >= 1; i--)//注意这里
{
while (st.size() && a[st.top()] <= a[i])
st.pop();
if (st.size())
ret[i] = st.top();
st.push(i);
}
for (int i = 1; i <= n; i++)
{
cout << ret[i] << " ";
}
cout << endl;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
test();
cout << endl;
}
2.4.寻找当前元素右侧第一个比当前元素小的元素
从右往左遍历元素，构造⼀个单调递增的栈。插⼊当前位置的元素的时：
如果栈为空，则左侧不存在⽐当前元素⼩的元素；
如果栈⾮空，插⼊当前位置元素时的栈顶元素就是所找的元素。
•注意，因为我们要找的是最终结果的位置。因此，栈⾥⾯存的是每个元素的下标。
这个代码其实很好写的，我们只能从栈顶往栈底一个一个出栈，只要我们把栈顶的那些>=当前元素的，那出现的第一个<当前元素的就一定是当前元素左侧第一个比当前元素小的元素了
#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], n;
int ret[N];
void test()
{
stack<int> st;
for (int i = n; i >= 1; i--)//注意这里
{
while (st.size() && a[st.top()] >= a[i])
st.pop();
if (st.size())
ret[i] = st.top();
st.push(i);
}
for (int i = 1; i <= n; i++)
{
cout << ret[i] << " ";
}
cout << endl;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
test();
cout << endl;
}
上面四种情况我给大家总结了一下：
题目一——P5788 【模板】单调栈 - 洛谷
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int nums[N];
int n;
int ret[N];
void test()
{
stack<int>s;
for(int i=n;i>=1;i--)
{
while(s.size()&&nums[s.top()]<=nums[i])
s.pop();
if(s.size())
ret[i]=s.top();
s.push(i);
}
for(int i=1;i<=n;i++)
{
cout<<ret[i]<<" ";
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>nums[i];
}
test();
cout<<endl;
}
很简单是吧
题目二——P1901 发射站 - 洛谷
说实话，这个还是很简单的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long LL;
LL V[N],H[N];
LL ret[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>H[i]>>V[i];
}
stack<int>s;
for(int i=1;i<=n;i++)
{
while(s.size()&&H[s.top()]<=H[i])
s.pop();
if(s.size())
ret[s.top()]+=V[i];
s.push(i);
}
while(s.size()) s.pop();
for(int i=n;i>=1;i--)
{
while(s.size()&&H[s.top()]<=H[i])
s.pop();
if(s.size())
ret[s.top()]+=V[i];
s.push(i);
}
LL retmax=0;
for(int i=1;i<=n;i++)
{
retmax=max(retmax,ret[i]);
}
cout<<retmax<<endl;
return 0;
}
题目三——SP1805 HISTOGRA - Largest Rectangle in a Histogram - 洛谷
其实很简单
#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]; // x[i]记录左边第一个比h[i]矮的索引，y[i]记录右边第一个比h[i]矮的索引
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();
// 记录右侧第一个比当前矮的索引（栈顶元素）
// 栈空表示右侧没有更矮的柱子，右边界设为n+1
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++) {
// 计算当前柱子能形成的最大矩形宽度：右边界-左边界-1
// 面积 = 高度 * 宽度
ret = max(ret, h[i] * (y[i] - x[i] - 1));
}
cout << ret << endl;
}
return 0;
}