【题目描述】
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度，但可以具有不同的高度。
例如，图例左侧显示了由高度为
2
,
1
,
4
,
5
,
1
,
3
,
3
2,1,4,5,1,3,3
2,1,4,5,1,3,3的矩形组成的直方图，矩形的宽度都为
1
1
1：
通常，直方图用于表示离散分布，例如，文本中字符的频率。
现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。
【输入格式】
输入包含几个测试用例。
每个测试用例占据一行，用以描述一个直方图，并以整数
n
n
n开始，表示组成直方图的矩形数目。
然后跟随
n
n
n个整数
h
1
,
…
,
h
n
h_1,dots ,h_n
h1,…,hn。
这些数字以从左到右的顺序表示直方图的各个矩形的高度。
每个矩形的宽度为
1
1
1。
同行数字用空格隔开。
当输入用例为
n
=
0
n=0
n=0时，结束输入，且该用例不用考虑。
【输出格式】
对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。
每个数据占一行。
请注意，此矩形必须在公共基线处对齐。
【数据范围】
1
≤
n
≤
1
0
5
1≤n≤10^5
1≤n≤105
0
≤
h
i
≤
1
0
9
0≤h_i≤10^9
0≤hi≤109
【输入样例】
7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0
【输出样例】
8 4000
【分析】
如下图所示，我们枚举每个高度 h i h_i hi，那么 i i i向左右延伸至第一个比 h i h_i hi低的位置后一定能围出一个高度为 h i h_i hi的面积最大的矩形，那么很容易想到复杂度为 O ( n 2 ) O(n^2) O(n2)的暴力做法，那么有什么数据结构能够优化复杂度呢？
找到某个数左边/右边第一个小于这个数的方式可以使用单调栈在 O ( n ) O(n) O(n)的时间复杂度预处理出来，因此我们可以使用 l [ i ] l[i] l[i]与 r [ i ] r[i] r[i]分别表示 i i i左边与右边第一个比 h i h_i hi低的位置，正向与反向遍历一遍构造出相应的单调栈预处理出这两个数组，最后再枚举一遍所有 h i h_i hi，答案在 h [ i ] ∗ ( r [ i ] − l [ i ] − 1 ) h[i]*(r[i]-l[i]-1) h[i]∗(r[i]−l[i]−1)中取最大值即可。
【代码】
#include#include #include using namespace std; typedef long long LL; const int N = 100010; int h[N], l[N], r[N];//l/r[i]表示i左/右边第一个比h[i]低的位置 int stk[N], tt; int n; int main() { while (cin >> n, n) { for (int i = 1; i <= n; i++) cin >> h[i]; h[0] = h[n + 1] = -1;//初始化边界 tt = 0, stk[0] = 0; for (int i = 1; i <= n; i++) { while (h[i] <= h[stk[tt]]) tt--;//由于存在边界所以栈一定非空 l[i] = stk[tt]; stk[++tt] = i; } tt = 0, stk[0] = n + 1; for (int i = n; i; i--) { while (h[i] <= h[stk[tt]]) tt--; r[i] = stk[tt]; stk[++tt] = i; } LL res = 0; for (int i = 1; i <= n; i++) res = max(res, (LL)h[i] * (r[i] - l[i] - 1)); cout << res << endl; } return 0; }
