考察点:从具体题上升到题型方法论——识别「两侧最近更小/更大元素」信号,并用哨兵简化边界。追问:为什么最大矩形题要在末尾加一个高度为 0 的哨兵柱?
要点:单调栈的通用画像是「对每个元素,求两侧第一个比它小(或大)的元素位置」;84 题把每个柱子当作「决定高度的那根」,用一次遍历同时确定左右边界。
def largestRectangleArea(h):
h = h + [0] # 右哨兵:强制清栈
stack, ans = [], 0
for i, x in enumerate(h):
while stack and h[stack[-1]] >= x:
height = h[stack.pop()]
left = stack[-1] if stack else -1
ans = max(ans, height * (i - left - 1))
stack.append(i)
return ans
题目与答案就在本页;收藏、批注和错题重练在应用内