2025年单调栈及其应用

大家好，我是讯享网，很高兴认识大家。

一、极简概念

二、几个栗子

1.糟糕的一天（洛谷P2866, USACO 2006 月赛）

2.天气变化

3.长方形（洛谷P1950）

一、极简概念

单调栈是一种内部元素具有单调性的栈，可以解决“以某个值为最值的最大区间”等问题。

能以O(n)的时间复杂度找到每一个元素右边或左边第一个比它大或小的数。（超级好用艾~ 不然可能就得用~~（毒瘤的）~~二分+RMQ惹QAQ）

来看几道题就会用了

二、几个栗子

1.糟糕的一天（洛谷P2866, USACO 2006 月赛）

传送门

讯享网

转变思路：与其求一头牛能看见几头牛，不如反过来，计算一头牛能被几头牛看见，因为它们的总和是相等的。一只牛能被哪些牛看到呢？左边比它高的牛，再左边更高的牛……只需要维护一个数组，满足这个数组里面存的都是对于第 i 头牛来说，身高一次递增的牛的身高（这个数组是单调递减的）。可以使用栈来进行维护。

假设有6头牛，高度分别为 10，3，7，4，12，2，那么它们分别可以看到 3，0 ，1，0，1，0头牛的头发，其总和为5；栈的实现：最开始栈是空的，原来栈里没有牛，那么答案增加0；身高为3的牛来了，从栈顶开始，把所有身高小于等于3的牛都出栈（这里暂时没有这样的牛），然后自己入栈，自己左边有一头牛，答案增加1；身高为7的牛来了，从栈顶开始，把所有小于等于7的牛都出栈（3就出栈），然后自己入栈，自己左边有一头牛，答案增加1……以此类推。

#include<iostream> #include<stack> using namespace std; long long ans; stack<int> s; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n;cin>>n; for(int i=1,x;i<=n;i++){ cin>>x; while(!s.empty()&&s.top()<=x)s.pop(); ans+=s.size(); s.push(x); } cout<<ans; return 0; }

讯享网

2.天气变化

CSUSTOJ | 天气变化

讯享网#include<iostream> #include<stack> using namespace std; const int M=1e6+6; int n,a[M]; struct nt{ int v,id; }p[M]; stack<nt> s; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n;cin>>n; for(int i=1;i<=n;i++)cin>>p[i].v,p[i].id=i; a[n]=0; s.push(p[n]); for(int i=n-1;i;i--){ while(!s.empty()&&s.top().v<=p[i].v)s.pop(); if(!s.empty())a[i]=s.top().id-i; else a[i]=0; s.push(p[i]); } for(int i=1;i<=n;i++)cout<<a[i]<<' '; return 0; }

3.长方形（洛谷P1950）

P1950 长方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

小明今天突发奇想，想从一张用过的纸中剪出一个长方形。

为了简化问题，小明做出如下规定：

（1）这张纸的长宽分别为 $n,m$。小明讲这张纸看成是由$n\times m$个格子组成，在剪的时候，只能沿着格子的边缘剪。

（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。

（3）剪出来的长方形的大小没有限制。

小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？

输入格式

第一行两个正整数 n,m，表示这张纸的长度和宽度。

接下来有 n 行，每行 m$个字符，每个字符为 `*` 或者 `.`。

字符 `*` 表示以前在这个格子上画过，字符 `.` 表示以前在这个格子上没画过。

输出格式

仅一个整数，表示方案数。

样例 1

样例输入 1
6 4
....
.*
.*..
.*
...*
.*

样例输出 1
38

书上咋又是数组模拟栈。。看着晕qwq。为啥不直接用stack啊

#include<iostream> #include<stack> using namespace std; const int M=1e3+6; int n,m,l[M],r[M]; struct nt{ int h,id; }p[M]; stack<nt> s; long long ans; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; char x; for(int i=1;i<=m;i++)p[i].id=i; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>x; p[j].h=(x=='*'?0:p[j].h+1); } while(!s.empty())s.pop(); for(int j=1;j<=m;j++){ while(!s.empty()&&s.top().h>p[j].h)s.pop(); if(!s.empty())l[j]=s.top().id; else l[j]=0; s.push(p[j]); } while(!s.empty())s.pop(); for(int j=m;j;j--){ while(!s.empty()&&s.top().h>=p[j].h)s.pop(); if(!s.empty())r[j]=s.top().id; else r[j]=m+1; s.push(p[j]); } for(int j=1;j<=m;j++) ans+=(j-l[j])*(r[j]-j)*p[j].h; } cout<<ans; return 0; }

emmmm记得清空栈那里别落了感叹号（非空啊）QAQ晚上捣鼓半天没发现www感谢pbrjjOrzzz

2025年单调栈及其应用

一、极简概念

二、几个栗子

1.糟糕的一天（洛谷P2866, USACO 2006 月赛）

2.天气变化

3.长方形（洛谷P1950）

相关推荐