LC84　柱状图中最大的矩形¶

困难通过率 49.8%python3核心代码模式栈样例通过牛客 AC栈数组单调栈区间最值查询

牛客原题　源码

讲解章节：单调栈

一句话

单调栈存下标，为每根柱子求出它能向两侧扩展的最大宽度。

解题思路¶

这题考什么¶

最大矩形一定可以按「高度等于某根柱子」来枚举：把答案矩形往上顶，直到碰到它覆盖范围内最矮的那根柱子，此时高度恰好等于那根柱子的高度。于是问题变成——对每根柱子 i，求以 heights[i] 为高时能横向铺多宽。

以 i 为高的矩形，左右两侧只要柱子不比 heights[i] 矮就能继续铺，碰到第一根更矮的就必须停。所以宽度由两个量决定：

left[i]  = i 左边第一根**严格更矮**的柱子的下标
right[i] = i 右边第一根**严格更矮**的柱子的下标
宽度 = right[i] - left[i] - 1，面积 = heights[i] * 宽度

「找左/右侧第一个更矮的元素」正是单调栈的标准用途（见单调栈）。维护一个栈，栈内下标对应的高度自底向上递增。新柱子 h 到来时，栈顶若不比 h 矮就必须出栈——对出栈的那根柱子而言，右边第一个更矮的就是当前位置 i，而左边第一个更矮的就是它出栈后新的栈顶，两侧边界在同一瞬间同时确定，一次弹栈就能算出它的完整面积。

栈里存的是下标而不是高度，因为宽度是两个位置之差；只存高度就算不出 right - left - 1，而高度随时可以用 heights[下标] 取回来。

两端各加一个哨兵可以省掉两次收尾清算：栈底预置下标 -1，当作「左边有一根高度为负无穷的柱子」。它永远不会出栈，于是任何一次弹栈之后栈都非空，左边界直接取 stack[-1]，不必写「栈空时左边界算 -1」的特判。右侧在扫描时多走一格 i == n，把那一格的高度当作 0（低于题面允许的最小高度 0 所能挡住的一切，等价于负无穷哨兵），迫使栈里剩余的柱子全部出栈结算，不必在循环外再写一遍相同的弹栈代码。

数据规模与复杂度¶

1 <= heights.length <= 1e5，0 <= heights[i] <= 1e4。每个下标入栈一次、出栈一次，时间 O(n)，空间 O(n)—— 高度严格递增（如 1, 2, 3, …）时栈会装下全部下标。朴素做法「枚举左右端点求区间最小值」是 O(n^2) 甚至 O(n^3)， n = 1e5 时 O(n^2) 就是 1e10 次操作，Python 下毫无可能。面积最大可达 1e5 * 1e4 = 1e9，Python 的 int 无上限，不必担心溢出；但用 C++ 的 int 写同样的算法会溢出，这是本题的经典陷阱。

坑在哪¶

栈里存下标，不存高度。面积要算 right - left - 1 这个宽度，只有下标能回答「隔了多远」。存高度的话弹栈时根本不知道该乘多少。
左边界取的是弹栈之后的新栈顶，不是被弹元素本身。顺序必须是「先 pop 记下 top，再读 stack[-1]」。写反（先读栈顶再 pop）会把被弹柱子自己当成左边界，宽度整体少算。
哨兵 -1 不能参与高度比较。判断条件里要先保证 len(stack) > 1，否则会去取 heights[-1]——Python 的负下标是合法的，它会悄悄取到 数组最后一个元素，不报错，只是结果莫名其妙地错。这是本题最隐蔽的坑。
弹栈条件用「大于等于」还是「大于」都能得到正确答案，但理由要清楚。用 >= 时，一串等高柱子中除最右那根外，每根算出的宽度都偏小；但最右那根出栈时左边界会一路越过所有等高的同伴，算出的正是完整宽度，最大值因此没有丢。用 > 则每根等高柱子都算不到完整宽度，反而需要额外处理，所以这里取 >=。
右侧哨兵的高度取 0 是安全的，因为题面给的高度下界就是 0，配合 >= 的弹栈条件，i == n 那一格能把栈里剩下的柱子全部逼出来。若弹栈条件是严格大于，高度为 0 的柱子就会赖在栈里不出来，必须改用负数哨兵。
高度可以是 0。全 0 的输入答案是 0，算法自然给出 0，不需要特判，但不要写出「面积至少为 heights[0]」之类的假设。
严格比对：最大面积是一个确定的数值，没有多解。

样例复核¶

heights = [2, 1, 5, 6, 2, 3]，n = 6，期望 10。栈初始为 [-1]。

i=0 h=2   栈顶哨兵，直接入      栈 = [-1, 0]
i=1 h=1   heights[0]=2 >= 1 弹 0：左边界 -1，宽 1-(-1)-1=1，面积 2*1=2
          栈 = [-1]，入 1        栈 = [-1, 1]
i=2 h=5   heights[1]=1 < 5 直接入 栈 = [-1, 1, 2]
i=3 h=6   直接入                 栈 = [-1, 1, 2, 3]
i=4 h=2   弹 3(高6)：左边界 2，宽 4-2-1=1，面积 6
          弹 2(高5)：左边界 1，宽 4-1-1=2，面积 10   <- 最大值在此产生
          heights[1]=1 < 2 停，入 4  栈 = [-1, 1, 4]
i=5 h=3   直接入                 栈 = [-1, 1, 4, 5]
i=6 h=0（右哨兵）
          弹 5(高3)：左边界 4，宽 6-4-1=1，面积 3
          弹 4(高2)：左边界 1，宽 6-1-1=4，面积 8
          弹 1(高1)：左边界 -1，宽 6-(-1)-1=6，面积 6
          栈只剩哨兵，停

最大面积 10，与题面一致。i=4 弹出下标 2 那一步正是整题的关键：高 5 的柱子向左能铺到下标 2、向右能铺到下标 3，宽 2 面积 10。

参考实现¶

solutions/leetcode/LC84/sol.py
from typing import List, Optional


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        # 单调栈：存**下标**，对应高度自底向上递增。存下标而非高度，
        # 是因为面积要用两个位置之差算宽度，高度随时能由 heights[下标] 取回。
        # 栈底预置哨兵 -1，代表「左边有一根无限矮的柱子」：它永不出栈，
        # 于是每次弹栈后栈都非空，左边界可以无脑取 stack[-1]
        stack = [-1]
        best = 0
        # 多走一格到 i == n，那一格当作高度 0 的右哨兵，
        # 逼出栈里剩余的全部柱子，省掉循环外重复一遍的收尾清算
        for i in range(n + 1):
            h = 0 if i == n else heights[i]
            # len(stack) > 1 是在保护哨兵：栈里只剩 -1 时不能再比，
            # 否则 heights[-1] 会取到数组最后一个元素——合法下标，不报错，结果却错
            while len(stack) > 1 and heights[stack[-1]] >= h:
                # 被弹的这根柱子，右边第一个更矮的就是当前位置 i，
                # 左边第一个更矮的是它出栈后的新栈顶——两侧边界同时确定
                top = stack.pop()
                # 先 pop 再读 stack[-1]，顺序不能反：左边界是新栈顶，
                # 不是被弹的 top 自己。宽度是两个边界之间的开区间长度
                width = i - stack[-1] - 1
                area = heights[top] * width
                if area > best:
                    best = area
            stack.append(i)
        return best

LC84 柱状图中最大的矩形¶