IT 面试题库

开放讨论:单调栈能解的题有什么共同画像?请以「柱状图中最大的矩形」(LeetCode 84)为例,说明单调栈如何在一次遍历中确定每个柱子的左右边界,以及哨兵技巧的作用。

高级开放讨论题算法工程师Java后端工程师单调栈柱状图最大矩形LeetCode84哨兵题型方法论

题目

考察点:从具体题上升到题型方法论——识别「两侧最近更小/更大元素」信号,并用哨兵简化边界。追问:为什么最大矩形题要在末尾加一个高度为 0 的哨兵柱?

参考答案

内容深度:详细 · 含示例/代码 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:单调栈的通用画像是「对每个元素,求两侧第一个比它小(或大)的元素位置」;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
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题