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

描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

示例 1:

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

示例 2:

输入： heights = [2,4]
输出： 4

提示

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

解题思路

详细题解见：

• 官方题解
• 栈（单调栈、哨兵技巧）

代码

不加哨兵的版本：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = Integer.MIN_VALUE;
        int n = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int index = stack.pop();
                res = stack.isEmpty() ? Math.max(res, i * heights[index]) : Math.max(res, (i - stack.peek() - 1) * heights[index]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int index = stack.pop();
            res = stack.isEmpty() ? Math.max(res, heights[index] * n) : Math.max(res, heights[index] * (n - stack.peek() - 1));
        }
        return res;
    }
}

加哨兵的版本：

import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        int res = 0;
        int[] newHeights = new int[n + 2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, n);
        newHeights[n + 1] = 0;
        heights = newHeights;
        n += 2;
        Deque<Integer> stack = new ArrayDeque<Integer>(n); 
        stack.addLast(0);

        for (int i = 1; i < n; i++) {
            while (heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(N)，输入数组里的每一个元素入栈一次，出栈一次。
• 空间复杂度：O(N)，栈的空间最多为 N。