单调栈例题思维导图
单调栈例题-好奇的鸣人（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; }
沪公网安备 31011502019485号
上海工商