84. 柱状图中最大的矩形

力扣题目链接 (opens new window)

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

思路

最直观的做法是什么？

枚举每一根柱子，把它作为矩形的高度，再分别向左、向右寻找第一根比它矮的柱子。两侧边界之间的柱子都不低于当前高度，因此可以计算矩形面积：

面积 = 当前柱子高度 × (右边界下标 - 左边界下标 - 1)

但每根柱子最坏都要扫描整个数组，时间复杂度是 O(n²)，会超时。

本题真正要找的是：每根柱子左侧和右侧第一个比它矮的柱子。

什么时候应该想到单调栈呢？

通常遇到“找一个元素左边或右边第一个比它大（或小）的元素”时，就应该想到单调栈。

栈里存什么

计算宽度需要使用下标，所以栈中存放柱子的下标，再通过下标取得柱子高度。

从左向右遍历，栈内下标对应的高度从栈底到栈顶保持单调不减。

什么时候计算面积

如果当前柱子不低于栈顶柱子，它还不能成为栈顶柱子的右边界，直接入栈。

如果当前柱子比栈顶柱子矮，说明栈顶柱子的右边界已经出现了。此时弹出栈顶，记弹出的下标为 mid：

• 当前下标 i 是 mid 右侧第一个更矮的位置
• 弹栈后的新栈顶是 mid 左侧的边界
• 矩形高度是 heights[mid]
• 矩形宽度是 i - stack.top() - 1

因此面积为：

heights[mid] × (i - stack.top() - 1)

弹出一根柱子后，当前柱子还可能比新的栈顶更矮，所以这里必须使用 while，而不是只判断一次。

图中栈顶柱子弹出后，新栈顶、弹出的柱子和当前柱子共同确定了矩形的左边界、高度和右边界。

为什么首尾补 0

如果柱子高度单调递增，例如 [2,4,6,8]，遍历过程中没有更矮的柱子触发弹栈，栈里的面积就无法计算。

在数组末尾补一个高度为 0 的柱子，就能让栈中剩余柱子全部弹出并计算面积。

如果柱子高度单调递减，例如 [8,6,4,2]，第一根柱子弹出后栈会变空，无法取得左边界。

所以数组开头也补一个 0，作为统一的左边界。这样就不需要在循环中额外判断空栈。

首尾两个 0 是哨兵：开头的 0 保证左边界存在，结尾的 0 负责清空栈。

对于相同高度，代码会让它们都留在栈中。较右的柱子先计算较窄的矩形，较左的柱子随后会计算包含全部相同高度柱子的更宽矩形，因此不会漏掉答案。

模拟过程

以 heights = [2,1,5,6,2,3] 为例，首尾补 0 后得到：

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

先把开头哨兵的下标 0 入栈，然后从下标 1 开始遍历：

1. 遇到高度 2，它高于栈顶的 0，下标入栈。
2. 遇到高度 1，弹出高度 2。此时宽度为 1，面积为 2 × 1 = 2。
3. 高度 5、6 依次入栈，栈内高度仍然单调不减。
4. 遇到高度 2，先弹出高度 6，面积为 6 × 1 = 6；继续弹出高度 5，其左右边界分别是高度 1 和当前高度 2，宽度为 2，面积为 5 × 2 = 10。
5. 高度 2、3 入栈。最后遇到结尾的 0，栈内剩余柱子依次弹出，得到的面积都不超过 10。

所以最大矩形由高度为 5 和 6 的两根柱子构成，最终答案是 10。

解题代码

C++

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> newHeights(heights.size() + 2, 0);
        for (int i = 0; i < heights.size(); i++) {
            newHeights[i + 1] = heights[i];
        }

        stack<int> st;
        st.push(0); // 左侧哨兵保证弹栈后仍能取得左边界
        int result = 0;

        for (int i = 1; i < newHeights.size(); i++) {
            while (newHeights[i] < newHeights[st.top()]) {
                int mid = st.top();
                st.pop();
                int width = i - st.top() - 1;
                result = max(result, newHeights[mid] * width);
            }
            st.push(i);
        }

        return result;
    }
};

复杂度分析

• 时间复杂度：O(n)。每个下标最多入栈一次、出栈一次。
• 空间复杂度：O(n)。新数组和单调栈最多存放 O(n) 个元素。

其他语言

Python3

from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        new_heights = [0] + heights + [0]
        stack = [0]
        result = 0

        for i in range(1, len(new_heights)):
            while new_heights[i] < new_heights[stack[-1]]:
                mid = stack.pop()
                width = i - stack[-1] - 1
                result = max(result, new_heights[mid] * width)
            stack.append(i)

        return result

Java

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

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int result = 0;

        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[i] < newHeights[stack.peek()]) {
                int mid = stack.pop();
                int width = i - stack.peek() - 1;
                result = Math.max(result, newHeights[mid] * width);
            }
            stack.push(i);
        }

        return result;
    }
}

Go

func largestRectangleArea(heights []int) int {
    newHeights := make([]int, len(heights)+2)
    copy(newHeights[1:], heights)

    stack := []int{0}
    result := 0

    for i := 1; i < len(newHeights); i++ {
        for newHeights[i] < newHeights[stack[len(stack)-1]] {
            mid := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            width := i - stack[len(stack)-1] - 1
            area := newHeights[mid] * width
            if area > result {
                result = area
            }
        }
        stack = append(stack, i)
    }

    return result
}

JS

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    const newHeights = [0, ...heights, 0];
    const stack = [0];
    let result = 0;

    for (let i = 1; i < newHeights.length; i++) {
        while (newHeights[i] < newHeights[stack[stack.length - 1]]) {
            const mid = stack.pop();
            const width = i - stack[stack.length - 1] - 1;
            result = Math.max(result, newHeights[mid] * width);
        }
        stack.push(i);
    }

    return result;
};

与代码随想录联系

我在代码随想录的84. 柱状图中最大的矩形中，还给出了暴力解法和预处理左右边界的双指针解法，并详细分析了单调栈的三种情况。

本题和以下题目放在一起学习，最容易看清单调栈的使用边界：

• 739. 每日温度：寻找右侧第一个更大的元素，是单调栈的入门题
• 42. 接雨水：寻找左右两侧第一个更大的元素，弹栈时计算凹槽中的雨水

接雨水找的是两侧第一个更高的柱子，本题找的是两侧更矮的边界。把这两道题对照起来，单调栈的顺序为什么相反，也就清楚了。