柱状图中的最大矩形面积怎么求？

直接回答：单调递增栈。以每根柱子为高，能构成的最大矩形宽度取决于它左右两侧第一根更矮柱子的位置。遍历中维护一个高度递增的下标栈，遇到更矮的柱子就弹栈结算：弹出的柱子为高，新栈顶（左边界）与当前下标（右边界）之间为宽。数组两端补 0 高度哨兵可免去栈空判断。每根柱子恰好进出栈一次，时间 O(n)、空间 O(n)。

展开解析：关键观察：一根柱子向左向右能延伸的宽度，由两侧「第一根比它矮」的柱子夹出；单调栈恰好按序维护了这个信息——当右墙出现（当前更矮柱）时，栈顶柱子的左右边界同时确定，立即结算。哨兵技巧（首尾各加一个高度 0）保证所有柱子都会被弹出结算且左边界恒存在，是工程上避免边界判断的常用手段。同族与追问：最大矩形（二维二进制矩阵，逐行转成柱状图调用本题解法，O(mn)）、 maximal square 用 DP；这题与接雨水常被对比——接雨水求「两侧最大值的瓶颈」，最大矩形求「两侧更矮值的边界」，对应单调栈的不同用法。

示例：

def largest_rectangle_area(heights):
    heights = [0] + heights + [0]      # 哨兵
    stack = [0]
    best = 0
    for i in range(1, len(heights)):
        while heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1      # 左右更矮柱之间
            best = max(best, h * w)
        stack.append(i)
    return best