剑指 Offer II 039. 直方图最大矩形面积
题目
给定非负整数数组 heights，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
- 1 <= heights.length <= 105
- 0 <= heights[i] <= 104
注意：本题与主站84题相同
题解
public int largestRectangleArea(int[] heights) {
int len = heights.length, area = 0;
// 若末尾不是0 补一个0 保证所有柱子都能被弹出
if (heights[len - 1] != 0) {
heights = Arrays.copyOfRange(heights, 0, len + 1);
len = heights.length;
}
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < len; i++) {
// 若当前柱子高度大于栈顶 则计算栈顶两个柱子之间的面积
while (stack.size() > 1 && heights[stack.peek()] >= heights[i]) {
area = Integer.max(area, heights[stack.pop()] * (i - stack.peek() - 1));
}
// 否则低柱子入栈
stack.push(i);
}
return area;
}