Hard

题目描述

给定一个整数数组 heights ，表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 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

解题思路

解题思路

这是一道经典的单调栈问题。核心思想是对于每个柱子，找到以它为高度的最大矩形面积。

暴力解法思路

对每个位置 i，向左右扩展找到第一个高度小于 heights[i] 的位置，计算以 heights[i] 为高度的矩形面积。时间复杂度 O(n²)。

单调栈优化思路（推荐）

使用单调递增栈来高效找到每个柱子左右两侧第一个更矮的柱子：

  1. 栈的作用：维护一个单调递增的柱子索引栈
  2. 入栈时机：当前柱子高度 >= 栈顶柱子高度时入栈
  3. 出栈计算：当前柱子高度 < 栈顶柱子高度时，说明找到了栈顶柱子的右边界，开始计算面积
  4. 左右边界：
    • 右边界：当前位置 i
    • 左边界：栈顶下一个元素（如果栈空则为 -1）
    • 宽度 = i - left - 1
    • 面积 = height * width

技巧优化

在数组末尾添加高度为 0 的柱子，确保所有柱子都能被处理到。

时间复杂度 O(n)，空间复杂度 O(n)，每个元素最多入栈出栈一次。

代码实现

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(0);  // 添加哨兵，确保所有柱子都被处理
        int maxArea = 0;
        
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        
        return maxArea;
    }
};

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        heights.append(0)  # 添加哨兵，确保所有柱子都被处理
        max_area = 0
        
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * w)
            stack.append(i)
        
        return max_area

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        Array.Resize(ref heights, heights.Length + 1);  // 添加哨兵
        heights[heights.Length - 1] = 0;
        int maxArea = 0;
        
        for (int i = 0; i < heights.Length; i++) {
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()]) {
                int h = heights[stack.Pop()];
                int w = stack.Count == 0 ? i : i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, h * w);
            }
            stack.Push(i);
        }
        
        return maxArea;
    }
}

var largestRectangleArea = function(heights) {
    let stack = [];
    let maxArea = 0;
    
    for (let i = 0; i <= heights.length; i++) {
        let currentHeight = i === heights.length ? 0 : heights[i];
        
        while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) {
            let height = heights[stack.pop()];
            let width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        
        stack.push(i);
    }
    
    return maxArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
暴力解法O(n²)O(1)
单调栈（推荐）O(n)O(n)

相关题目