84 柱状图中最大的矩形

一、题目

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

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

二、题解

方法一：单调栈一次遍历

思路：单调栈。

1. 核心思路

对于每一根柱子，如果将它的高度作为矩形的高度，那么需要知道它最多能够向左和向右扩展多远。

例如，当前柱子的高度为 5：

[2, 1, 5, 6, 2, 3]
       ↑

它右边的柱子 6 不低于它，因此可以向右扩展。

但是继续向右遇到高度为 2 的柱子，因为 2 < 5，所以不能继续扩展。

因此，以高度 5 为矩形高度时：

高度 = 5
宽度 = 2
面积 = 5 × 2 = 10

为了快速找到每根柱子左右两侧第一个比它矮的柱子，可以使用单调栈。

栈中保存柱子的下标，并且保证对应的柱子高度从栈底到栈顶单调递增。

核心思想是：

  • 当当前柱子的高度大于等于栈顶柱子时，当前柱子仍然可以入栈；
  • 当当前柱子比栈顶柱子矮时，说明栈顶柱子不能继续向右扩展；
  • 此时弹出栈顶，并计算以弹出柱子高度为矩形高度时的面积；
  • 弹栈后的新栈顶就是左边第一个比弹出柱子矮的位置；
  • 当前下标就是右边第一个比弹出柱子矮的位置。

为了让最后留在栈中的柱子也能够被计算，可以在数组末尾虚拟添加一根高度为 0 的柱子。

2. 具体步骤

  1. 创建一个单调栈，栈中存储柱子的下标。
  2. 从左到右遍历柱子，并额外遍历一次下标 n。
  3. 当遍历到下标 n 时，将当前柱子高度看作 0。
  4. 如果当前柱子高度小于等于栈顶柱子的高度，就不断弹出栈顶。
  5. 对于每个被弹出的柱子：
    • 它的高度就是当前矩形的高度；
    • 当前下标 i 是右边第一个更矮的位置；
    • 弹栈后的新栈顶是左边第一个更矮的位置。
  6. 根据左右边界计算矩形宽度和面积。
  7. 不断更新最大面积。
  8. 将当前柱子的下标压入栈中。
  9. 遍历结束后返回最大面积。

3. 关键逻辑

while (!stack.isEmpty()
        && heights[stack.peek()] >= currentHeight) {

    // 弹出的柱子作为矩形高度
    int height = heights[stack.pop()];

    // 弹栈后的栈顶是左边第一个更矮的位置
    int left = stack.isEmpty() ? -1 : stack.peek();

    // 当前下标 i 是右边第一个更矮的位置
    int width = i - left - 1;

    maxArea = Math.max(maxArea, height * width);
}

解释：

  • 如果当前柱子比栈顶柱子矮，说明栈顶柱子不能继续向右扩展；
  • 当前下标 i 就是栈顶柱子右边第一个更矮的位置；
  • 弹栈后的新栈顶就是左边第一个更矮的位置；
  • 左右两个更矮的位置都不能包含在矩形中；
  • 因此矩形宽度为：
width = i - left - 1

假设：

heights = [2, 1, 5, 6, 2, 3]

遍历到下标 4、高度 2 时，栈顶柱子的高度为 6：

弹出高度 6：

左边第一个更矮的位置：下标 2，高度 5
右边第一个更矮的位置：下标 4，高度 2

宽度 = 4 - 2 - 1 = 1
面积 = 6 × 1 = 6

继续弹出高度 5：

左边第一个更矮的位置：下标 1，高度 1
右边第一个更矮的位置：下标 4，高度 2

宽度 = 4 - 1 - 1 = 2
面积 = 5 × 2 = 10

最终得到最大面积 10。

4. 代码

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

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 1. 处理特殊情况
        if (heights == null || heights.length == 0) {
            return 0;
        }

        // 2. 定义需要使用的变量和单调栈
        int n = heights.length;
        int maxArea = 0;

        // 栈中存储柱子的下标
        // 对应的柱子高度保持单调递增
        Deque<Integer> stack = new ArrayDeque<>();

        // 3. 核心逻辑
        // 遍历到 n 时，虚拟添加一根高度为 0 的柱子
        for (int i = 0; i <= n; i++) {
            int currentHeight = i == n ? 0 : heights[i];

            /*
             * 当前柱子小于等于栈顶柱子时：
             * 说明栈顶柱子的右边界已经确定，
             * 可以弹出栈顶并计算面积。
             */
            while (!stack.isEmpty()
                    && heights[stack.peek()] >= currentHeight) {

                // 当前弹出的柱子作为矩形高度
                int height = heights[stack.pop()];

                /*
                 * 弹栈后的新栈顶是左边第一个更矮的位置。
                 * 如果栈为空，说明左边没有更矮的柱子，
                 * 将左边界记为 -1。
                 */
                int left = stack.isEmpty() ? -1 : stack.peek();

                /*
                 * 当前下标 i 是右边第一个更矮的位置。
                 * 左右边界都不能包含在矩形中。
                 */
                int width = i - left - 1;
                int area = height * width;

                maxArea = Math.max(maxArea, area);
            }

            // 当前柱子入栈
            stack.push(i);
        }

        // 4. 返回结果
        return maxArea;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每根柱子最多入栈一次、出栈一次，因此所有栈操作的总次数为 O(n)O(n)。

虽然代码中存在 for 循环和 while 循环，但同一个下标不会被重复弹栈，所以整体时间复杂度仍然是 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：最坏情况下，所有柱子按照递增顺序排列，所有下标都会进入栈中，因此栈最多存储 nn 个下标。

方法二：单调栈预处理左右边界

思路：使用两个单调栈过程，分别计算每根柱子左边和右边第一个比它矮的位置。

1. 核心思路

方法一是在遍历过程中，当柱子出栈时直接计算面积。

方法二先分别计算每根柱子的左右边界：

left[i]：下标 i 左边第一个严格小于 heights[i] 的柱子下标

right[i]：下标 i 右边第一个严格小于 heights[i] 的柱子下标

得到左右边界后，以 heights[i] 作为矩形高度时，矩形能够覆盖的范围是：

(left[i], right[i])

由于左右边界位置的柱子都比当前柱子矮，因此不能包含在矩形中。

矩形宽度为：

right[i] - left[i] - 1

矩形面积为：

heights[i] × (right[i] - left[i] - 1)

这种方法的核心是：

  • 从左向右遍历，计算左边第一个更矮的位置；
  • 从右向左遍历，计算右边第一个更矮的位置；
  • 枚举每根柱子作为矩形高度；
  • 根据左右边界计算最大面积。

2. 具体步骤

  1. 创建数组 left 和 right。
  2. 将所有 left[i] 初始化为 -1，表示左边没有更矮的柱子。
  3. 将所有 right[i] 初始化为 n，表示右边没有更矮的柱子。
  4. 从左向右遍历：
    • 弹出所有高度大于等于当前柱子的下标；
    • 弹栈后的栈顶就是左边第一个更矮的位置；
    • 将当前下标压入栈中。
  5. 清空栈。
  6. 从右向左遍历：
    • 弹出所有高度大于等于当前柱子的下标；
    • 弹栈后的栈顶就是右边第一个更矮的位置；
    • 将当前下标压入栈中。
  7. 枚举每根柱子，根据左右边界计算矩形面积。
  8. 返回最大的矩形面积。

3. 关键逻辑

// 计算左边第一个严格更矮的位置
while (!stack.isEmpty()
        && heights[stack.peek()] >= heights[i]) {
    stack.pop();
}

left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);

解释：

  • 如果栈顶柱子的高度大于等于当前柱子，它就不是当前柱子左边第一个严格更矮的位置；
  • 因此需要将它弹出；
  • 弹栈结束后，如果栈不为空，栈顶就是左边第一个严格更矮的位置；
  • 如果栈为空，说明左边没有更矮的柱子，将边界记为 -1。

计算右边界的过程与左边界类似，只需要从右向左遍历：

// 计算右边第一个严格更矮的位置
while (!stack.isEmpty()
        && heights[stack.peek()] >= heights[i]) {
    stack.pop();
}

right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);

得到左右边界后，面积计算公式为：

int width = right[i] - left[i] - 1;
int area = heights[i] * width;

4. 代码

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

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 1. 处理特殊情况
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int n = heights.length;

        // 2. 前置处理
        /*
         * left[i]：左边第一个严格小于 heights[i] 的位置
         * right[i]：右边第一个严格小于 heights[i] 的位置
         */
        int[] left = new int[n];
        int[] right = new int[n];

        // 默认左边界为 -1，右边界为 n
        Arrays.fill(left, -1);
        Arrays.fill(right, n);

        // 3. 定义单调栈
        Deque<Integer> stack = new ArrayDeque<>();

        // 4. 核心逻辑

        // 从左向右计算左边第一个更矮的位置
        for (int i = 0; i < n; i++) {
            /*
             * 高度大于等于当前柱子的下标都要弹出，
             * 保证栈顶柱子严格小于当前柱子。
             */
            while (!stack.isEmpty()
                    && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }

            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }

            stack.push(i);
        }

        // 计算右边界之前先清空栈
        stack.clear();

        // 从右向左计算右边第一个更矮的位置
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty()
                    && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }

            if (!stack.isEmpty()) {
                right[i] = stack.peek();
            }

            stack.push(i);
        }

        // 根据左右边界计算最大矩形面积
        int maxArea = 0;

        for (int i = 0; i < n; i++) {
            int width = right[i] - left[i] - 1;
            int area = heights[i] * width;

            maxArea = Math.max(maxArea, area);
        }

        // 5. 返回结果
        return maxArea;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：

  • 从左向右遍历一次，时间复杂度为 O(n)O(n)；
  • 从右向左遍历一次，时间复杂度为 O(n)O(n)；
  • 最后计算所有柱子的面积，时间复杂度为 O(n)O(n)。

每根柱子在每次单调栈遍历中最多入栈一次、出栈一次，因此总时间复杂度为 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：使用了长度为 nn 的 left 数组、right 数组以及单调栈，因此空间复杂度为 O(n)O(n)。

评论