HDU 1506 Largest Rectangle in a Histogram(最大矩形面积、单调栈)

题目链接：
HDU 1506 Largest Rectangle in a Histogram
题意：
给出一排紧密并列的矩形的高，宽均为1，求从中可以划分出的最大的矩形面积？
数据范围：$n\leq 10^5,h_i\leq 10^{9}$
分析：
单调栈求出每个矩形可以向左向右延伸的最大长度。
单调栈、单调队列学习博客
时间复杂度:$O(n)$

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int n;
ll height[MAX_N];
int L[MAX_N], R[MAX_N], sta[MAX_N];int main()
{while (~scanf("%d", &n) && n) {for (int i = 1; i <= n; ++i) {scanf("%lld", &height[i]);}height[0] = height[n + 1] = 0;int top = 0, cur;for(int i = 1; i <= n + 1; ++i) {while(1) {cur = sta[top];if (height[cur] <= height[i]) break;R[cur] = i;top--;}cur = sta[top];L[i] = cur;sta[++top] = i;}ll ans = 0;for(int i = 1; i <= n; ++i) {int len = R[i] - L[i] - 1;ans = max(ans, height[i] * len);}printf("%lld\n", ans);}return 0;
}