单调栈例题思维导图_编号w1195983-TreeMind树图

笔灵AI论文写作三步搞定，GO>>

当前位置:树图

思维导图模板

资格考试

计算机

单调栈例题思维导图

免费下载

免费使用文件

Mr.Xu

浏览量：2

2023-07-17 16:56:49

已被使用0次

查看详情

单调栈例题-好奇的鸣人（P1318:积水面积）

树图思维导图提供单调栈例题在线思维导图免费制作，点击“编辑”按钮，可对单调栈例题进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：60afd12b943121b47a9f39a238332320

单调栈例题

举报/反馈

思维导图大纲

单调栈例题-好奇的鸣人（P1318:积水面积）思维导图模板大纲

法一

暴力-双重循环

双重循环遍历每个节点左边，右边最大比他大的，找其中的较小值（水总不可能悬空存）然后减当前节点高度（如果没有比它大的就是0）

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],cnt=0; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ int maxn=-1,maxs=-1; for(int j=1;j<=i-1;j++) maxn=max(a[j],maxn); for(int j=i+1;j<=n;j++) maxs=max(a[j],maxs); if(min(maxs,maxn)-a[i]>=0)cnt+=min(maxs,maxn)-a[i]; } cout<<cnt; return 0; }

法二

暴力前缀和思想优化

本质上就是法一的优化，空间换时间，提前预处理好每一个节点左边，右边比它大的，然后直接用

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],cnt=0,maxl[N],maxr[N]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); maxr[n]=a[n],maxl[1]=a[1]; for(int i=2;i<=n;i++) maxl[i]=max(a[i],maxl[i-1]); for(int i=n-1;i>=1;i--) maxr[i]=max(a[i],maxr[i+1]); for(int i=1;i<=n;i++) cnt+=max(0,min(maxl[i],maxr[i])-a[i]); cout<<cnt; return 0; }

法三

双指针

用两个指针l,r再用maxl,maxr分别找l，r节点左边，右边比它大的，选较小值记录

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int l=1,r=n,maxl=-1,maxr=-1,cnt=0; while(l<r){ maxl=max(maxl,a[l]); maxr=max(maxr,a[r]); if(maxl<maxr) cnt+=maxl-a[l++]; else cnt+=maxr-a[r--]; } printf("%d",cnt); return 0; }

法四

单调栈

用单调栈找每个障碍物左边第一个比它高的位置累两加障碍物之间的储雨量

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N]; stack<int> s; int main(){ int n,cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ int last=0; while(!s.empty()){ if(a[s.top()]<a[i]){ cnt+=(a[s.top()]-last)*(i-s.top()-1); last=a[s.top()]; s.pop(); } else break; } if(!s.empty()) cnt+=(a[i]-last)*(i-s.top()-1); s.push(i); } cout<<cnt; return 0; }