模拟单调栈

例题1：链接：http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1329

有n个数，每个数有权值。数学老师定义了区间价值为区间和乘上区间内的最小值。

现在要你找出有最大区间价值的区间是什么，并输出区间价值

输入：

每个输入文件只包含单组数据。
第一行一个整数n。(1 <= n <= 100000)
第二行n个整数a_1,a_2,...,a_n。(0 <= a_i <= 1000000)

输出：

第一行输出一个整数，表示最大的区间价值。
第二行输出两个整数，表示区间的起点和终点。
保证答案唯一。

Sample Input：

10 1 9 4 5 9

Sample Output：

108

3 6

此题求区间和，以及区间的最小值，我们可以使用单调栈的思想

设定L[]数组，记录以a[i]为最小值的左边边界；

设定R[]数组，记录以a[i]为最小值的右边边界；

这样，样例中的L，R数组为

位置：1 2 3 4 5 6

10 1 9 4 5 9

L 1 2 3 3 5 6

R 1 6 3 6 6 6

这样，我们就可以通过计算 R[i]-L[i] 来得出区间的范围，代码怎么实现呢？

以上代码为模拟单调栈的核心代码

由于区间价值是区间和*区间的最小值，所以我们要算出区间和，在这里我们使用前缀和

读取数据时计算：

算出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
",ans);
    printf("%lld %lld
",l,r);
    return 0;
}

View Code

例题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
",sum1);
   }
    return 0;
}

View Code

祝大家都能AC~