给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
在本题中，要求最大矩形面积。思路为找到以height[i]为宽的矩形的长。即面积=height[i]*(right[i]-left[i]+1)。为题转化为通过单调栈求得left[i]和right[i]。
求right[i]时，栈中存的索引，当height[i]小于stack.peek索引所代表的长度时，i不可以作为right[stack.peek]，也就是说可以确定right[stack.peek]为i的前一位。执行stack.poll，之后再次查看height[i]与height[stack.peek]的大小。
left[i]也是同理。代码如下。
package Leetcode;
import java.util.Stack;
public class largestRectangleArea {
public int largestRectangleArea(int[] heights) {
if (heights.length == 0) {
return 0;
}
if (heights.length == 1) {
return heights[0];
}
int[] left = new int[heights.length];
int[] right = new int[heights.length];
//栈中存储索引
Stack<Integer> stack = new Stack<>();
//为right[]赋值
for (int i = 0; i < heights.length; i++) {
if (stack.isEmpty()) {
stack.add(i);
continue;
}
//若存入后栈依然单调，则入栈
if (heights[i] >= heights[stack.peek()]) {
stack.add(i);
} else {
//若存入后破坏了单调性，则弹出栈中对应的height小于height[i]的，并且可以知道他们的right。
int num = stack.peek();
while ((!stack.isEmpty()) && (heights[i] < heights[stack.peek()])) {
right[stack.peek()] = num;
stack.pop();
}
stack.add(i);
}
}
//最终未从栈中弹出意味着没有比他更小的值了，right为heights.length-1
while (!stack.isEmpty()) {
int index = stack.pop();
right[index] = heights.length - 1;
}
//为left[]赋值
for (int i = heights.length - 1; i >= 0; i--) {
if (stack.isEmpty()) {
stack.add(i);
continue;
}
if (!stack.isEmpty() && heights[i] >= heights[stack.peek()]) {
stack.add(i);
} else {
int index = stack.peek();
while ((!stack.isEmpty()) && (heights[i] < heights[stack.peek()])) {
left[stack.peek()] = index;
stack.pop();
}
stack.add(i);
}
}
int res = 0;
for (int i = 0; i < heights.length; i++) {
res = Math.max(res, heights[i] * (right[i] - left[i] + 1));
}
return res;
}
}
原文：https://www.cnblogs.com/zhangbochao/p/13033908.html