F_矩形面积

F_矩形面积

方法：单调栈

思路：

单调栈是具有单调性的栈，为了维护单调性就需要每次入栈前判断待入元素与栈顶元素的大小，将小于（单调递减栈）或大于（单调递增栈）的栈顶元素拿出后放入当前元素。

（有没有发现调整判定与单调性一致，单调递减就需要把栈顶小于当前元素的都拿出来，单调递增就需要把大于当前元素的都拿出来）

应用：寻找在左边或右边第一个大于或小于当前目标的元素

（单调递增栈用于寻找左右第一个小于的元素，单调递减栈用于寻找左右第一个大于的元素）

（丑丑的代码）

#include <stdio.h>
#define N 100000
typedef long long int i64;

int main(void)
{
    i64 n;
    scanf("%lld", &n);
    i64 stack[N] = {0}, a[N];
    i64 L[N] = {0};
    i64 R[N] = {0};
    i64 top = -1, p = -1;
    for (i64 i = 0; i < n + 1; i++)
    {
        if (i != n)
            scanf("%d", &a[i]);
        else
            a[i] = 0;
        while (top != -1 && a[p] >= a[i])
        {
            R[p] = i;
            top--;
            if (top != -1)
                p = stack[top];
        }
        L[i] = p;
        stack[++top] = i;
        p = stack[top];
    }
    i64 max = 0, s = 0;
    i64 l, r;
    for (i64 i = 0; i < n; i++)
    {
        l = L[i];
        r = R[i];
        if (l == -1)
        {
            s = (r - 1) * a[i];
            max = (s > max) ? s : max;
        }
        else
        {
            s = (r - l - 1) * a[i];
            max = (s > max) ? s : max;
        }
    }
    printf("%lld\n", max);
    return 0;
}