51nod1215数组的宽度(单调栈)

1215 数组的宽度

题目来源： Javaman

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

N个整数组成的数组，定义子数组a[i]..a[j]的宽度为：max(a[i]..a[j]) - min(a[i]..a[j])，求所有子数组的宽度和。

Input

第1行：1个数N，表示数组的长度。(1 <= N <= 50000)
第2 - N + 1行：每行1个数，表示数组中的元素(1 <= A[i] <= 50000)

Output

输出所有子数组的宽度和。

Input示例

5
1
2
3
4
5

Output示例

20

这题的主要思路是求出每个数字作为最大的数作用的范围，根据这个范围求出作为最大的数被计算了多少次。同理也需要求作为最小被计算了多少次。

因此需要计算每个数作为最大数的左边界和右边界。在这里可以使用单调队列或单调栈的方法，

以1 5 4 2 3为例，逐个入栈计算每个数的右边界：

1入栈 => 1

5入栈，前面所有比5小的出栈，并将右边界设为5 => 5 (确定了1的右边界是5，对应下标为1)

4入栈，前面所有比4小的出栈，并将右边界设为4 => 5 4

2入栈，前面所有比2小的出栈，并将右边界设为2 => 5 4 2

3入栈，前面所有比3小的出栈，并将右边界设为3 => 5 4 3(确定了2的右边界是3，对应下标为4)

最后所有数出栈，将5 4 3这3个数的右边界的下标设为5。

这样可以确认，每个数字最多进一次栈出一次栈，所有复杂度是O(n)的。

计算左边界以及作为最小数的左右边界的方法类似。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define N 50005
int a[N], stk[N];
int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        a[++n]=0;
        LL ans1=0, ans2=0;
        int top=0;
        for(int i=1; i<=n; i++)
        {
            while(top&&a[i]<a[stk[top]])
            {
                ans1+=1LL*(stk[top]-stk[top-1])*(i-stk[top])*a[stk[top]];
                top--;
            }
            stk[++top]=i;
        }
        a[n]=N;
        top=0;
        for(int i=1; i<=n; i++)
        {
            while(top&&a[i]>a[stk[top]])
            {
                ans2+=1LL*(stk[top]-stk[top-1])*(i-stk[top])*a[stk[top]];
                top--;
            }
            stk[++top]=i;
        }
        printf("%I64d\n", ans2-ans1);
    }
    return 0;
}