剑指 Offer II 039. 直方图最大矩形面积

题目

给定非负整数数组 heights,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:
示例1
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:
示例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;
}