例题1：链接：http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1329
有n个数，每个数有权值。数学老师定义了区间价值为区间和乘上区间内的最小值。
以上代码为模拟单调栈的核心代码
由于区间价值是区间和*区间的最小值，所以我们要算出区间和，在这里我们使用前缀和
读取数据时计算：
算出R[i]、L[i]后；
接下来的比较我就不说明了~
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6; ll sum[maxn]; int L[maxn],R[maxn]; int a[maxn]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]+=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) { int l=i; while(a[i]<=a[l-1]&&l>1) //判断左边以a[i]为最小值能到哪 { l=L[l-1]; //如果比a[l-1]要小，那么它能到达以a[l-1]为最小值的左边 } L[i]=l; } for(int i=n;i>=1;i--) { int r=i; while(a[i]<=a[r+1]&&r<n) //判断右边以a[i]为最小值能到哪 { r=R[r+1];//如果比a[r+1]要小，那么它能到达以a[r+1]为最小值的右边 } R[i]=r; } ll ans = -1,l,r; for(int i=1;i<=n;i++) { ll res=(sum[R[i]]-sum[L[i]-1])*a[i]; if(res>ans) { ans=res; l=L[i]; r=R[i]; } } printf("%lld\n",ans); printf("%lld %lld\n",l,r); return 0; }
例题2：链接：https://ac.nowcoder.com/acm/problem/15815
这道题可以学完上面之后加以强化
注意：
1、计算求和区间的最大值与最小值的差=求出所有区间的最大值-所有区间的最小值==（以a[i]为最大值的区间*区间数）-（以a[i]为最小值的区间*区间数）
2、类似1 3 1出现重复值序列，使用一次 = 判断即可，不然会减去多一个重复值
3、数组不要太大，容易内存超限！
4、int *int 会出现溢出，因此计算时最好化为 ll ~
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+5; int L[maxn],R[maxn]; int a[maxn]; int main() { int n; while(~scanf("%d",&n)) { memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { int l=i; while(a[i]<a[l-1]&&l>1) //判断左边以a[i]为最小值能到哪 { l=L[l-1]; //如果比a[l-1]要小，那么它能到达以a[l-1]为最小值的左边 } L[i]=l; } for(int i=n;i>=1;i--) { int r=i; while(a[i]<=a[r+1]&&r<n) //判断右边以a[i]为最小值能到哪 { r=R[r+1];//如果比a[r+1]要小，那么它能到达以a[r+1]为最小值的右边 } R[i]=r; } ll sum1=0; for(int i=1;i<=n;i++) { sum1-=(ll(i-L[i]+1)*(R[i]-i+1))*a[i]; } //***************************************** for(int i=1;i<=n;i++) { int l=i; while(a[i]>a[l-1]&&l>1) //判断左边以a[i]为最大值能到哪 { l=L[l-1]; //如果比a[l-1]要大，那么它能到达以a[l-1]为最小值的左边 } L[i]=l; } for(int i=n;i>=1;i--) { int r=i; while(a[i]>=a[r+1]&&r<n) //判断右边以a[i]为最大值能到哪 { r=R[r+1];//如果比a[r+1]要大，那么它能到达以a[r+1]为最小值的右边 } R[i]=r; } for(int i=n;i>=1;i--) { sum1+=(ll(i-L[i]+1)*(R[i]-i+1))*a[i]; } printf("%lld\n",sum1); } return 0; }
祝大家都能AC~
原文：https://www.cnblogs.com/acmer-hmin/p/11748087.html
