题目描述

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

解题思路

本题要求计算柱状图中能勾勒出的最大矩形面积，是单调栈的经典应用。

核心思路是：对于每一根柱子，如果我们以它的高度作为矩形的高，那么我们需要找到它左右两边第一个比它矮的柱子，这两个柱子之间的宽度就是该矩形可以扩展的最大宽度。

单调栈解法：

  1. 预处理：在原数组的首尾各添加一个高度为 0 的哨兵柱子。这样做的好处是：

    • 头部哨兵确保栈永远不会为空（stack.peek() 始终有效）
    • 尾部哨兵确保遍历结束后，栈中所有柱子都会出栈计算面积

  2. 维护单调递增栈：栈中存储的是下标，对应的高度值单调递增。遍历每个柱子 i：

    • 当当前柱子的高度小于栈顶柱子的高度时，说明栈顶柱子的”右边界”已经找到了。弹出栈顶，以该柱子的高度作为矩形高，宽度为 i - left - 1（其中 left 是弹出后新的栈顶），计算面积并更新最大值。
    • 重复上述过程，直到栈顶柱子高度不大于当前柱子，然后将当前柱子下标入栈。

  3. 单调栈的本质：栈中始终保持着高度递增的柱子序列。当遇到一个更矮的柱子时，它意味着栈中所有比它高的柱子都无法继续向右扩展了，这些柱子可以依次出栈并计算以它们为高度的最大矩形面积。

每个柱子只会入栈和出栈一次，因此总体的时间复杂度为 O(n)。

复杂度分析

  • 时间复杂度：O(n)，每个元素最多入栈一次，出栈一次。
  • 空间复杂度：O(n)，单调栈和扩展后的数组都需要 O(n) 的空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package code.J84;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class J84 {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        heights = newHeights;
        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                int left = stack.peek();
                int width = i - left - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }
        return max;
    }
}