进阶数据结构——单调栈
目录
- 一、 基本概念
- 二、 单调栈的类型
- 三、应用场景
- 四、 实现步骤
- 五、 复杂度分析
- 六、 注意事项
- 七、代码模版（c++）
- 八、经典例题
- 伦太郎的等待
- 百亿富翁
- [ 最大区间](https://www.lanqiao.cn/problems/17152/learning/?page=1&first_category_id=1&name=%E6%9C%80%E5%A4%A7%E5%8C%BA%E9%97%B4)
- 九、总结
一、 基本概念
单调栈是一种特殊的栈结构，栈内元素保持单调递增或递减。常用于解决需要找到元素左侧或右侧第一个比它大或小的元素的问题。
二、 单调栈的类型
• 单调递增栈：栈内元素从栈底到栈顶递增。
• 单调递减栈：栈内元素从栈底到栈顶递减。
三、应用场景
• 下一个更大元素：找到数组中每个元素右侧第一个比它大的元素。
• 下一个更小元素：找到数组中每个元素右侧第一个比它小的元素。
• 最大矩形面积：在直方图中找到最大矩形面积。
• 滑动窗口最大值：在滑动窗口中找到最大值。
四、 实现步骤
以下一个更大元素为例：
- 初始化一个空栈。
- 遍历数组中的每个元素：
◦ 当栈不为空且当前元素大于栈顶元素时，弹出栈顶元素并记录当前元素为栈顶元素的下一个更大元素。
◦ 将当前元素压入栈中。 - 遍历结束后，栈中剩余元素没有下一个更大元素。
五、 复杂度分析
时间复杂度：O(n)，每个元素最多入栈和出栈一次。
空间复杂度：O(n)，栈的大小最多为n。
六、 注意事项
确保栈的单调性，根据问题需求选择递增或递减栈。
处理边界条件，如空栈或数组末尾元素。
七、代码模版（c++）
#include<iostream>
#include<stack>
using namespace std;
#define maxn 50001
#define inf 2000000000
template<typename T>
bool cmp(T a, T b) {
return a >= b;
}
template<typename T>
void findFirstGreaterOnLeft(int n, T h[], int ans[]) {
h[0] = inf;
stack<int>stk;
stk.push(0);
for (int i = 1; i <= n; i++) {
while ( !cmp(h[stk.top()], h[i])) {
stk.pop();
}
ans[i] = stk.top();
stk.push(i);
}
}
template<typename T>
void reverseArray(int n, T arr[]) {
for (int i = 1; i <= n / 2; i++) {
T t = arr[i];
arr[i] = arr[n - i + 1];
arr[n - i + 1] = t;
}
}
int h[maxn], ans[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
findFirstGreaterOnLeft(n, h, ans);
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << endl;
return 0;
}
八、经典例题
伦太郎的等待
#include<iostream>
#include<stack>
using namespace std;
#define maxn 100001
#define inf 2000000000
template<typename T>
bool cmp(T a, T b) {
return a >= b;
}
template<typename T>
void reverse(int n, T h[]) {
for (int i = 1; i <= n / 2; i++) {
T t = h[i];
h[i] = h[n - i + 1];
h[n - i + 1] = t;
}
}
template<typename T>
void findFirstGreaterOnLeft(int n, T h[], int ans[]) {
stack<int>stk;
stk.push(0);
h[0] = inf;
for (int i = 1; i <= n; i++) {
while (!cmp(h[stk.top()], h[i])) {
stk.pop();
}
ans[i] = stk.top();
stk.push(i);
}
}
double h[maxn];int ans[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
findFirstGreaterOnLeft(n, h, ans);
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += i - 1 - ans[i];
}
cout << cnt << endl;
return 0;
}
百亿富翁
#include<iostream>
#include<stack>
using namespace std;
#define maxn 700001
#define inf 2000000000
template<typename T>
bool cmp(T a, T b) {
return a > b;
}
template<typename T>
void reverseArr(int n, T h[]) {
for (int i = 1; i <= n / 2; i++) {
T t = h[i];
h[i] = h[n - i + 1];
h[n - i + 1] = t;
}
}
template<typename T>
void findFirstGreaterOnLeft(int n, T h[], int ans[]) {
stack<int>stk;
stk.push(0);
h[0] = inf;
for (int i = 1; i <= n; i++) {
while (!cmp(h[stk.top()], h[i])) {
stk.pop();
}
ans[i] = stk.top();
stk.push(i);
}
}
double h[maxn];int ans[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
findFirstGreaterOnLeft(n, h, ans);
for (int i = 1; i <= n; i++) {
if (ans[i] == 0)ans[i] = -1;
cout << ans[i] << ' ';
}
cout << endl;
reverseArr(n, h);
findFirstGreaterOnLeft(n, h, ans);
reverseArr(n, ans);
for (int i = 1; i <= n; i++) {
if (ans[i] == 0)ans[i] = -1;
else ans[i] = (n + 1) - ans[i];
cout << ans[i] << ' ';
}
cout << endl;
return 0;
}
最大区间
#include<iostream>
#include<stack>
using namespace std;
#define maxn 300001
#define inf -1
template<typename T>
bool cmp(T a, T b) { //题目要求(R-L+1)*a[i]尽可能求最大值
return a < b; //因为题目要求说尽可能求得最大值，那么我们就找左边和右边第一个小的值，再把它们去掉
}
template<typename T> //反转数组的目的就是为了找右边第一个大的值
void reverseArr(int n, T h[]) {
for (int i = 1; i <= n / 2; i++) {
T t = h[i];
h[i] = h[n - i + 1];
h[n - i + 1] = t;
}
}
template<typename T>
void findFirstGreaterOnLeft(int n, T h[], int ans[]) {
stack<int>stk;
stk.push(0);
h[0] = inf;
for (int i = 1; i <= n; i++) {
while (!cmp(h[stk.top()], h[i])) {
stk.pop();
}
ans[i] = stk.top();
stk.push(i);
}
}
double h[maxn]; int l[maxn], r[maxn];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
findFirstGreaterOnLeft(n, h, l);
reverseArr(n, h);
findFirstGreaterOnLeft(n, h, r);
reverseArr(n, h);
reverseArr(n, r);
for (int i = 1; i <= n; i++) {
r[i] = n + 1 - r[i];
}
long long max = 0;
for (int i = 1; i <= n; i++) {
long long x = (r[i] - 1) - (l[i] + 1) + 1; //把这两个值去掉后就是要找的范围
x = x * h[i];
if (x > max)max = x;
}
cout << max << endl;
return 0;
}
九、总结
单调栈是一种高效的数据结构，适用于解决特定类型的问题。通过维护栈的单调性，可以快速找到元素之间的关系，提升算法效率。
希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
