P2659 美丽的序列 - 单调栈

题目
不断求区间的最值问题，就用单调栈，记录每个数前面第一次出现比自己小的数的小白
然后遍历右区间对于右区间左边，最小值是stk[top]，即栈顶，而stk[top - 1]就是stk[top]左边第一个比stk[top]小的值
那么区间就是\([stk[top - 1] + 1, i]\)，区间最小值就是a[stk[top]]
但注意的是，我们在单调栈出栈的操作中求最大值，此时右区间i的值还没有放进去，那么久需要把区间大小减1
同时还需要变量一下栈，因为此时栈是一个单调递增的栈，再按照上面的方法求，只不过右区间是n

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N = 2e6 + 5;
ll a[N], stk[N], ans[N], top, n;
int main(){
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	ll ans = 0;
	for(int i = 1; i <= n; i++){
        while(a[stk[top]] > a[i] && top){
           	ans = max(ans, a[stk[top]] * (i - stk[top - 1] - 1));
            top--;
        }
        stk[++top] = i;//入栈 
    }
	for(int i = 1; i <= top; i++)
		ans = max(ans, a[stk[i]] * (n - stk[i - 1]));
	printf("%lld\n", ans);
	return 0;
}
···

P2659 美丽的序列 - 单调栈

原文：https://www.cnblogs.com/Emcikem/p/12924828.html