[Leetcode 84] 柱状图中最大的矩形

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给出n个非负整数,用来表示柱状图中各个柱子的高度。
每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
 
示例 1:
notion image
示例 2:
notion image

解法一:暴力穷举

把任意一个矩形用“左右端点”唯一确定:对所有区间 [i,j][i, j][i,j](包含两端),矩形高度就是这段的最小高度,面积
因为重复扫描最小值,会造成时间爆炸。
复杂度
  • 时间:O(n^2),会超时
  • 空间:O(1)

解法一:中心扩展

固定一根柱子 i,以它的高度为矩形高度,最大可扩展宽度由“它左边第一个比它小的位置”与“右边第一个比它小的位置”决定。
  • 为左边第一个高度 < heights[i] 的索引
  • 为右边第一个高度 < heights[i] 的索引
则以 i 为最矮的最大矩形面积:
对每个i,向左/右线性走,直到遇到更小者为止。
复杂度
  • 时间:最坏 O(n^2)
  • 空间:O(n)

解法二:中心扩展

如果 ,那“左边第一个比 heights[i] 小的位置”其实与“左边第一个比 heights[j] 小的位置”是同一个(或更左),因为 i 更矮或相同,能挡住它的也能挡住 j。
因此,向左退时可以跳到 left[j],而不是 j−1;同理向右跳到 right[j]。这让每个位置至多被跳过有限次,整体摊还为 O(n)。
复杂度
  • 时间:O(n)
  • 空间:O(n)

解法三:单调栈(推荐)

维护一个严格单调递增的索引栈(按高度递增):
  • 栈内从底到顶:对应柱高 严格递增
  • 当遇到一个新柱子高度 ≤\le≤ 栈顶高度时,意味着以“栈顶那根柱子”为最矮形成的最大矩形的右边界已经找到了:就是当前索引
    • 与此同时,“左边界”则是出栈后的新栈顶(因为它是左边第一个更小的)。
  • 因此,弹栈即结算面积:
    • 高度 = 被弹出柱子的高度
    • 宽度 = 当前索引−新栈顶索引−1\text{当前索引} - \text{新栈顶索引} - 1当前索引−新栈顶索引−1
为简化边界,常在首尾两端补 哨兵 0,确保所有柱子在末尾都能被统一弹出结算,同时避免栈空越界。
复杂度
  • 时间:O(n),每个索引最多入栈/出栈各一次
  • 空间:O(n),栈
上一篇
[Leetcode 83] 删除排序链表中的重复元素
下一篇
[Leetcode 88] 合并两个有序数组