题目描述
直方图是由在公共基线处对齐的一系列矩形组成的多边形。
矩形具有相等的宽度,但可以具有不同的高度。
例如,图例左侧显示了由高度为 2,1,4,5,1,3,3 的矩形组成的直方图,矩形的宽度都为 1:
通常,直方图用于表示离散分布,例如,文本中字符的频率。
现在,请你计算在公共基线处对齐的直方图中最大矩形的面积。
图例右图显示了所描绘直方图的最大对齐矩形。
输入格式
输入包含几个测试用例。
每个测试用例占据一行,用以描述一个直方图,并以整数 n 开始,表示组成直方图的矩形数目。
然后跟随 n 个整数 h1,…,hn。
这些数字以从左到右的顺序表示直方图的各个矩形的高度。
每个矩形的宽度为 1。
同行数字用空格隔开。
当输入用例为 n=0 时,结束输入,且该用例不用考虑。
输出格式
对于每一个测试用例,输出一个整数,代表指定直方图中最大矩形的区域面积。
每个数据占一行。
请注意,此矩形必须在公共基线处对齐。
数据范围
1≤n≤100000,
0≤hi≤1000000000
样例
输入样例:
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出样例:
8
4000
Java 代码
import java.util.*;
import java.io.*;
public class Main{
// 暴力做法: 以每个矩形的高度为准,向两边扩展,直到遇到比它矮的为止,记录每个矩形向两侧扩展的边界[l,r]
// 扩展出的矩形面积为(r−l+1)∗h,h为当前柱子高度,时间复杂度为O(n^2)
// 单调栈:
static final int N = 100000;
public static void main(String[] agrs) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] inputs = reader.readLine().split(" ");
ArrayDeque<Integer> q = new ArrayDeque<>(N + 2);
int[] h = new int[N + 2]; // 记录每个柱子的高度(从下标1开始)
int[] l = new int[N + 2]; // l[i]表示第i个柱子左侧第一个比其低的柱子的位置(从下标1开始)
int[] r = new int[N + 2]; // r[i]表示第i个柱子右侧第一个比其低的柱子的位置(从下标1开始)
h[0] = -1; // 将左边界初始化为-1
while(Integer.parseInt(inputs[0]) != 0){
int n = Integer.parseInt(inputs[0]);
h[n + 1] = -1; // 将右边界初始化为-1
for(int i = 1; i <= n; i++){
h[i] = Integer.parseInt(inputs[i]);
}
q.push(0);
// 找出当前柱子左侧第一个比其高度低的柱子的位置
// 维持一个单调递增栈,栈顶元素为当前元素左侧第一个比其低的柱子的位置
for(int i = 1; i <= n; i++){
while(h[i] <= h[q.peek()]){
q.pop();
}
l[i] = q.peek();
q.push(i);
}
q.clear();
q.push(n + 1);
// 找出当前柱子右侧第一个比其高度低的柱子的位置
// 维持一个单调递增栈,栈顶元素为当前元素右侧第一个比其低的柱子的位置
for(int i = n; i >= 1; i--){
while(h[i] <= h[q.peek()]){
q.pop();
}
r[i] = q.peek();
q.push(i);
}
long result = 0;
for(int i =1; i <= n; i++){
result = Math.max(result, (long)h[i] * (r[i] - l[i] - 1));
}
writer.write(result + "\n");
inputs = reader.readLine().split(" ");
}
writer.flush();
}
}