LeetCode 84. 柱状图中最大的矩形
字数 1713 2025-10-27 08:13:40
LeetCode 84. 柱状图中最大的矩形
题目描述
给定一个非负整数数组 heights，表示柱状图中每个柱子的高度，每个柱子的宽度为 1。请找出柱状图中能够勾勒出的最大矩形的面积。
例如：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形是高度为 5 和 6 的柱子组成的区域（第 3 和第 4 根柱子），宽度为 2，面积为 5 × 2 = 10。
解题思路
核心问题是：对于每个柱子，找到它作为矩形高度时能扩展的最大宽度。宽度由左右两侧第一个比它矮的柱子位置决定。
- 暴力法：对每个柱子，向左/右扫描直到遇到更矮的柱子，计算宽度。时间复杂度 O(n²)，会超时。
- 单调栈优化：通过一次遍历记录每个柱子的左右边界，将时间复杂度降至 O(n)。
步骤详解（单调栈解法）
-
问题转化
对于柱子i，若以其高度heights[i]作为矩形高度，则需找到左右边界：- 左边界
left[i]：左侧第一个比heights[i]矮的柱子的索引（若没有，则为 -1）。 - 右边界
right[i]：右侧第一个比heights[i]矮的柱子的索引（若没有，则为 n）。 - 宽度 =
right[i] - left[i] - 1，面积 =heights[i] × 宽度。
- 左边界
-
单调栈的作用
- 栈内保存柱子的索引，且对应的高度单调递增。
- 遍历时，若当前柱子高度小于栈顶柱子的高度，则栈顶柱子的右边界确定为当前索引，左边界为栈内下一个索引（若栈空则为 -1）。
- 通过一次遍历可同时求出所有柱子的左右边界。
-
具体步骤
- 初始化栈
stack，数组left和right（初始值 -1 和 n）。 - 遍历索引
i从 0 到 n-1：- 若栈非空且
heights[i] < heights[stack[-1]]，则弹出栈顶元素top，并设置right[top] = i。 - 设置
left[i]为栈顶索引（若栈空则为 -1），然后将i入栈。
- 若栈非空且
- 遍历结束后，若栈非空，依次弹出并设置
right[top] = n。 - 计算每个柱子的面积：
maxArea = max(maxArea, heights[i] × (right[i] - left[i] - 1))。
- 初始化栈
-
示例演示（heights = [2,1,5,6,2,3]）
- 初始：
stack = [],left = [-1,-1,-1,-1,-1,-1],right = [6,6,6,6,6,6]。 - i=0：栈空，
left[0] = -1，入栈[0]。 - i=1：高度 1 < 2，弹出 0，
right[0] = 1；栈空，left[1] = -1，入栈[1]。 - i=2：高度 5 > 1，
left[2] = 1，入栈[1,2]。 - i=3：高度 6 > 5，
left[3] = 2，入栈[1,2,3]。 - i=4：高度 2 < 6，弹出 3，
right[3] = 4；高度 2 < 5，弹出 2，right[2] = 4；栈顶为 1，高度 1 < 2，left[4] = 1，入栈[1,4]。 - i=5：高度 3 > 2，
left[5] = 4，入栈[1,4,5]。 - 遍历结束，弹出栈内元素：
right[5]=6,right[4]=6,right[1]=6。 - 计算面积：
- i=0: 2×(1-(-1)-1)=2
- i=1: 1×(6-(-1)-1)=6
- i=2: 5×(4-1-1)=10 ← 最大
- i=3: 6×(4-2-1)=6
- i=4: 2×(6-1-1)=8
- i=5: 3×(6-4-1)=3
- 初始：
-
复杂度分析
- 时间复杂度：O(n)，每个元素入栈、出栈一次。
- 空间复杂度：O(n)，用于栈和边界数组。
关键点总结
- 单调栈帮助快速找到每个柱子左右第一个更矮的柱子。
- 注意遍历结束后栈内剩余元素的右边界处理。
- 此方法可推广到类似问题（如最大正方形、容器盛水问题）。