目录

单调栈

例题

破题点

代码

单调栈常见应用场景

1. 下一个更大元素

2. 前一个更小元素

3. 最大矩形问题

4. 股票买卖问题

单调栈

1.单调栈不是一种新的栈结构，它在结构上仍是一个普通的栈，它只是栈的一种使用方法，始终保持栈内的元素是单调的，常用来解决比较问题

2.当一个数入栈，和栈顶比较，若比栈顶小，则入栈；比栈顶大，则出栈，直到这个数能入栈为止

注意，每个数都一定入栈！单调栈比单调队列简单，栈只有一个出入口（单调队列可见上一篇博客）

这样说可能还是有点抽象， 接下来将从例题入手，详细介绍单调栈的使用及应用场景

例题

P2947 [USACO09MAR] Look Up S - 洛谷

乍一看很简单，但是如果用暴力求解，大数据就会直接TLE

破题点

1.比大小的题目常联想到栈结构

//新入栈的只有比前面的大，才会对前面的造成影响

//还没有遇到更大的就一直入栈，碰到小峰值后：栈更新+清空栈

2.用单调栈解题，单调栈很适合解决这种局部单调性的题

3.单调栈的时间复杂度是 O(N)，因为每个元素最多被压入和弹出栈一次

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10e5 + 10;
struct Node {
	int val;
	int see=0;//仰望对象
}node[N];
stack<Node*>s;//比较大小
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> node[i].val;
		//新入栈的只有比前面的大，才会对前面的造成影响
		//还没有遇到更大的就一直入栈，碰到小峰值后：栈更新+清空栈
		//出栈才有机会更新，只有碰到比自己大的才能出栈
		if (s.empty() || node[i].val <= s.top()->val) s.push(&node[i]);
		else {
			while (!s.empty() && node[i].val > s.top()->val)
			{
				s.top()->see = i;
				s.pop();
			}
			s.push(&node[i]);
		}
	}
	for (int i = 1; i <= n; i++) cout << node[i].see << endl;
}

单调栈常见应用场景

1. 下一个更大元素

• 问题描述：对于数组中的每个元素，找到它右边第一个比它大的元素。

• 应用场景：

  • 股票价格的“买入点”和“卖出点”。

  • 柱状图中的“最大矩形”问题。

• 解决方法：使用单调递增栈，栈中存储元素的索引。

2. 前一个更小元素

• 问题描述：对于数组中的每个元素，找到它左边第一个比它小的元素。

• 应用场景：

  • 计算表达式中的括号匹配。

  • 计算柱状图中的“最大矩形”问题。

• 解决方法：使用单调递减栈，栈中存储元素的索引。

3. 最大矩形问题

• 问题描述：在柱状图中找到最大的矩形面积。

• 应用场景：

  • 计算二维平面上的最大矩形面积。

  • 计算二维平面上的最大子矩阵和。

• 解决方法：使用单调递增栈，栈中存储柱子的索引。

4. 股票买卖问题

• 问题描述：给定一个数组，表示每天的股票价格，找到买入和卖出的最佳时机。

• 应用场景：

  • 计算股票的最大收益。

  • 计算股票的多次买卖最大收益。

• 解决方法：使用单调递增栈，栈中存储价格的索引。