H、小A的柱状图（单调栈）

https://ac.nowcoder.com/acm/contest/549/H

题意，求立方图的最大面积

单调递增栈，当不满足单调增时，将不满足的中间元素出栈，并以这个元素为左端点，导致它不满足单调性的点为右端点，更新最大的矩形面积。

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000005], h[1000005];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= n; i++)
		scanf("%lld", &h[i]);
	stack<ll>st;
	st.push(0);
	ll ans = 0;
	for (int i = 1; i <= n + 1; i++)
	{
		while (h[st.top()] > h[i])
		{
			ll index = st.top();
			st.pop();
			ll cnt = a[i - 1] - a[st.top()];
			ans = max(ans, cnt * h[index]);
		}
		st.push(i);
	}
	printf("%lld", ans);
}