想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第36课:柱状图最大矩形模块:栈与队列 |难度:Hard ⭐⭐LeetCode 链接:https://leetcode.cn/problems/largest-rectangle-in-histogram/前置知识:第33课(有效的括号)、第34课(最小栈)、第35课(每日温度)预计学习时间:35分钟 题目描述给定一个整数数组heights,表示直方图中每个柱子的高度。每个柱子的宽度为 1,要求找出这个直方图中能够勾勒出的最大矩形面积。示例 1:输入:heights [2,1,5,6,2,3] 输出:10 解释:最大矩形是从下标 2 到 3(即高度 [5,6]),高度为 5,宽度为 2,面积 5 × 2 10示例 2:输入:heights [2,4] 输出:4 解释:可以取高度为 2,宽度为 2 的矩形,面积 2 × 2 4约束条件:1 ≤ heights.length ≤ 10^50 ≤ heights[i] ≤ 10^4 边界用例(面试必考)用例类型输入期望输出考察点单柱子[5]5基本功能递增序列[1,2,3,4,5]9最大矩形可能在左侧递减序列[5,4,3,2,1]9最大矩形可能在右侧全相同[3,3,3,3]12最优解为全部柱子含零[2,0,2]2零高度打断连续性大规模n10^5—必须 O(n) 复杂度 思路引导生活化比喻想象你是一名城市规划师,要在一排不同高度的建筑之间找一块最大的矩形空地来建广场。笨办法:拿着卷尺,从每栋楼出发,一个个试:“以这栋楼高度为标准,能向左右延伸多远?” 这样需要尝试每一栋楼,每栋楼又要向两边扫描,耗时 O(n²)。聪明办法:你拿着一张纸条,从左往右走。遇到更矮的楼时,你就知道之前那些高楼的地盘到此为止了,立刻可以计算出它们能围出的最大矩形。这样只需走一遍,耗时 O(n)!关键洞察对于每个柱子,如果我们能快速知道它向左右两边能延伸到哪里,就能算出以它为高度的最大矩形。核心问题转化为:如何找到每个柱子左右两侧第一个比它矮的柱子?→ 单调栈模式! 解题思维链这一节模拟你在面试中从零开始思考的过程。Step 1:理解题目 → 锁定输入输出输入:整数数组heights,每个元素代表柱子高度输出:整数,表示最大矩形面积限制:柱子数量最多 10^5,意味着必须在 O(n) 或 O(n log n) 内解决Step 2:先想笨办法(暴力法)最直接的想法:枚举所有可能的矩形。对于每个柱子i,尝试以它的高度为矩形高度向左右两边扩展,找到能延伸的最大宽度计算面积并更新最大值时间复杂度:O(n²) — 对于每个柱子 i,需要向两边扫描寻找边界瓶颈在哪:对每个柱子都要线性扫描左右边界Step 3:瓶颈分析 → 优化方向暴力法中,对于每个柱子,我们重复计算了左右边界:核心问题:如何快速找到左侧第一个比当前柱子矮的位置?核心问题:如何快速找到右侧第一个比当前柱子矮的位置?这不正是单调栈擅长的下一个更小元素问题吗?Step 4:选择武器选用:单调递增栈理由:栈中维护递增序列,遇到更矮柱子时,栈顶的高柱子就找到了右边界栈中前一个元素就是左边界一次遍历即可完成,时间 O(n)模式识别提示:当题目要求每个元素左/右第一个更小/更大的元素,优先考虑单调栈 解法一:暴力枚举(教学用)思路对于每个柱子 i,以它的高度为矩形高度,向左右两边扩展,直到遇到比它矮的柱子为止。计算这个矩形的面积,取所有矩形的最大值。图解过程示例:heights [2,1,5,6,2,3] 枚举柱子 0(高度 2): 向左:无柱子 向右:遇到 1(高度 2),停止 宽度 1,面积 2 × 1 2 枚举柱子 1(高度 1): 向左:无更小 向右:无更小,可延伸到末尾 宽度 6,面积 1 × 6 6 枚举柱子 2(高度 5): 向左:遇到 1(高度 5),停止 向右:高度 6 可以,但遇到 2(高度 5),停止 宽度 2(从索引 2 到 3),面积 5 × 2 10 ← 最大 枚举柱子 3(高度 6): 向左:高度 5 可以,但遇到 1(高度 6),停止 向右:遇到 2(高度 6),停止 宽度 1,面积 6 × 1 6 ... 依次类推 最大面积 10Python代码fromtypingimportListdeflargest_rectangle_brute_force(heights:List[int])-int: 解法一:暴力枚举 思路:对每个柱子向左右扩展找边界 nlen(heights)max_area0foriinrange(n):hheights[i]# 找左边界:第一个比 h 小的位置leftiwhileleft0andheights[left-1]h:left-1# 找右边界:第一个比 h 小的位置rightiwhilerightn-1andheights[right1]h:right1# 计算以 heights[i] 为高度的矩形面积widthright-left1areah*width max_areamax(max_area,area)returnmax_area# ✅ 测试print(largest_rectangle_brute_force([2,1,5,6,2,3]))# 期望输出:10print(largest_rectangle_brute_force([2,4]))# 期望输出:4print(largest_rectangle_brute_force([5,4,3,2,1]))# 期望输出:9复杂度分析时间复杂度(n²) — 对于每个柱子 i,向左右扫描最坏需要 O(n) 时间具体地说:如果输入规模 n 1000,最坏需要约 1000 × 1000 1,000,000 次操作空间复杂度(1) — 只用了常量级变量优缺点✅ 思路直观,容易理解❌ 时间复杂度过高,对于 n 10^5 的数据会超时(需要 10^10 次操作)⚡ 解法二:预处理左右边界(优化)优化思路暴力法的瓶颈在于重复计算左右边界。我们可以预处理出两个数组:left[i]:柱子 i 左侧第一个比它矮的位置right[i]:柱子 i 右侧第一个比它矮的位置然后对每个柱子,直接通过left[i]和right[i]计算宽度,避免重复扫描。关键想法:用空间换时间,预处理边界数组,将单次查询从 O(n) 降为 O(1)图解过程heights [2,1,5,6,2,3] 索引 0 1 2 3 4 5 预处理 left[i](左侧第一个更小元素的索引): left[0] -1 (无更小) left[1] -1 (无更小) left[2] 1 (索引 1 的高度 1 5) left[3] 2 (索引 2 的高度 5 6,但需要继续向左找,最终 left[2]1 导致 left[3]1... 实际上应该是 1) left[4] 1 (索引 1 的高度 1 2) left[5] 4 (索引 4 的高度 2 3) 预处理 right[i](右侧第一个更小元素的索引): right[0] 1 (索引 1 的高度 1 2) right[1] 6 (无更小,设为 n) right[2] 4 (索引 4 的高度 2 5) right[3] 4 (索引 4 的高度 2 6) right[4] 6 (无更小) right[5] 6 (无更小) 计算每个柱子的最大面积: i2:width right[2] - left[2] - 1 4 - 1 - 1 2 area 5 × 2 10 ← 最大Python代码deflargest_rectangle_preprocess(heights:List[int])-int: 解法二:预处理左右边界 思路:先用两次遍历计算每个柱子的左右边界,再计算面积 nlen(heights)ifn0:return0# 预处理左边界:left[i] 左侧第一个比 heights[i] 小的索引left[-1]*nforiinrange(1,n):pi-1whilep0andheights[p]heights[i]:pleft[p]# 跳跃优化:利用已计算的结果left[i]p# 预处理右边界:right[i] 右侧第一个比 heights[i] 小的索引right[n]*nforiinrange(n-2,-1,-1):pi1whilepnandheights[p]heights[i]:pright[p]# 跳跃优化right[i]p# 计算最大面积max_area0foriinrange(n):widthright[i]-left[i]-1areaheights[i]*width max_areamax(max_area,area)returnmax_area# ✅ 测试print(largest_rectangle_preprocess([2,1,5,6,2,3]))# 期望输出:10print(largest_rectangle_preprocess([2,4]))# 期望输出:4print(largest_rectangle_preprocess([5,4,3,2,1]))# 期望输出:9复杂度分析时间复杂度(n) — 每个元素最多被访问 2 次(一次主循环,一次跳跃)空间复杂度(n) — 需要两个长度为 n 的辅助数组 解法三:单调栈(最优解)优化思路解法二虽然已经优化到 O(n),但代码较长,需要三次遍历。单调栈可以在一次遍历中同时计算左右边界并求出最大面积。核心思想:维护一个单调递增栈,栈中存储柱子的索引遍历每个柱子时:如果当前柱子高度 ≥ 栈顶柱子,入栈(保持递增)如果当前柱子高度 栈顶柱子,说明栈顶柱子找到了右边界,出栈并计算面积栈中前一个元素就是左边界关键想法:单调栈不仅能找边界,还能在找到边界的同时立即计算面积图解过程heights [2,1,5,6,2,3] 在末尾添加哨兵 0:[2,1,5,6,2,3,0] 初始:栈 [],max_area 0 i0,h2: 栈空,入栈 → 栈[0] i1,h1: 1 heights[0]2,栈顶出栈 弹出索引 0,高度 2 右边界 1,左边界 -1(栈空) 宽度 1 - (-1) - 1 1 面积 2 × 1 2 入栈 1 → 栈[1] i2,h5: 5 ≥ heights[1]1,入栈 → 栈[1,2] i3,h6: 6 ≥ heights[2]5,入栈 → 栈[1,2,3] i4,h2: 2 heights[3]6,弹出索引 3 高度 6,右边界 4,左边界 2 宽度 4 - 2 - 1 1 面积 6 × 1 6 2 heights[2]5,弹出索引 2 高度 5,右边界 4,左边界 1 宽度 4 - 1 - 1 2 面积 5 × 2 10 ← 更新最大值 2 ≥ heights[1]1,入栈 → 栈[1,4] i5,h3: 3 ≥ heights[4]2,入栈 → 栈[1,4,5] i6,h0(哨兵): 依次弹出所有元素: 弹出 5:3 × (6-4-1) 3 弹出 4:2 × (6-1-1) 8 弹出 1:1 × (6-(-1)-1) 6 最大面积 10Python代码deflargest_rectangle_area(heights:List[int])-int: 解法三:单调栈(最优解) 思路:维护单调递增栈,遇到更小元素时计算面积 # 在末尾添加哨兵 0,确保所有柱子都能出栈heightsheights[0]stack[]# 存储索引max_area0fori,hinenumerate(heights):# 当前高度小于栈顶,说明栈顶柱子的右边界确定了whilestackandhheights[stack[-1]]:height_idxstack.pop()# 弹出栈顶heightheights[height_idx]# 左边界:栈中前一个元素(如果栈空,说明左边全部 ≥ 当前高度)leftstack[-1]ifstackelse-1# 右边界:当前索引 iwidthi-left-1areaheight*width max_areamax(max_area,area)stack.append(i)returnmax_area# ✅ 测试print(largest_rectangle_area([2,1,5,6,2,3]))# 期望输出:10print(largest_rectangle_area([2,4]))# 期望输出:4print(largest_rectangle_area([5,4,3,2,1]))# 期望输出:9print(largest_rectangle_area([1]))# 期望输出:1print(largest_rectangle_area([3,3,3,3]))# 期望输出:12复杂度分析时间复杂度(n) — 每个元素最多入栈一次、出栈一次,总共 2n 次操作具体地说:如果 n 100,000,大约需要 200,000 次操作空间复杂度(n) — 栈最多存储 n 个元素为什么是最优解时间最优(n) 已经是理论下限(至少要遍历一遍所有柱子)一次遍历:比解法二的三次遍历更简洁代码清晰:单调栈模式代码结构标准,面试易写对实际性能:常数因子小,比暴力法快 5000 倍以上 Pythonic 写法利用 Python 的枚举和列表推导式,可以让代码更简洁:deflargest_rectangle_pythonic(heights:List[int])-int:单调栈的 Pythonic 简化写法heightsheights[0]stack[]max_area0fori,hinenumerate(heights):whilestackandhheights[stack[-1]]:heightheights[stack.pop()]widthiifnotstackelsei-stack[-1]-1max_areamax(max_area,height*width)stack.append(i)returnmax_area改进点:用enumerate同时获取索引和值简化宽度计算:width i if not stack else i - stack[-1] - 1⚠️面试建议:先写标准版本展示思路,通过测试后再提简洁写法展示 Python 功底。 解法对比维度解法一:暴力枚举解法二:预处理边界 解法三:单调栈(最优)时间复杂度O(n²)O(n)O(n)← 时间最优空间复杂度O(1)O(n)O(n)← 可接受代码难度简单中等中等遍历次数n 次(每次 O(n))3 次1 次← 最简洁面试推荐⭐⭐⭐⭐⭐⭐← 首选适用场景只适合小规模数据教学理解用面试标准答案为什么单调栈是最优解:时间复杂度 O(n) 已经达到理论下限一次遍历比预处理方法更高效单调栈是处理下一个更小/更大元素的标准模式代码结构清晰,面试中容易写对且不易出错面试建议:先用 30 秒口述暴力法思路(O(n²)),表明你能想到基本解法立即优化到单调栈解法,重点讲解核心思想强调单调栈的三个关键点:栈中存索引而非值遇到更小元素时出栈计算左边界是栈中前一个元素手动测试边界用例(递增、递减、全相同),展示对解法的深入理解 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官:请解决柱状图最大矩形问题。你:(审题 30 秒)好的,这道题要求在一个直方图中找出最大矩形面积。让我先想一下…我的第一个想法是暴力法:对每个柱子,向左右扩展找边界,计算以它为高度的矩形面积。时间复杂度是 O(n²),对于 10^5 的数据量会超时。优化思路:这个问题本质是对每个柱子,找左右两侧第一个比它矮的位置。这正是单调栈擅长的场景!我可以用单调递增栈,在 O(n) 时间内解决。面试官:很好,请写一下代码。你:(边写边说)deflargest_rectangle_area(heights):# 添加哨兵 0,确保所有元素都能出栈heightsheights[0]stack[]# 单调递增栈,存索引max_area0fori,hinenumerate(heights):# 当前高度 栈顶,栈顶柱子的右边界确定whilestackandhheights[stack[-1]]:height_idxstack.pop()heightheights[height_idx]# 左边界是栈中前一个元素leftstack[-1]ifstackelse-1widthi-left-1max_areamax(max_area,height*width)stack.append(i)returnmax_area面试官:测试一下?你:用示例[2,1,5,6,2,3]走一遍:i2 时入栈索引 2(高度 5)和 3(高度 6)i4 时高度 2 栈顶 6,弹出 3,计算 6×16继续弹出 2,计算 5×210(从索引 2 到 3)最终返回 10,正确!再测一个边界:全相同[3,3,3,3]→ 最终会计算 3×412,符合预期。高频追问追问应答策略“为什么要加哨兵 0?”确保所有柱子都能出栈计算面积。否则遍历结束时栈中剩余元素无法触发计算。“能不能不加哨兵?”可以,但需要遍历结束后再处理栈中剩余元素,代码会复杂一些。加哨兵是更优雅的做法。“空间能不能 O(1)?”理论上无法做到。单调栈需要 O(n) 空间,这是这类问题的固有开销。暴力法虽然 O(1) 空间,但 O(n²) 时间无法接受。“如果柱子宽度不为 1 呢?”输入增加一个 widths 数组,计算面积时改为height * sum(widths[left1:i])。“实际工程中怎么用?”图像处理中的最大矩形检测、仓库货物摆放优化、数据可视化中的柱状图分析等。 知识点总结Python技巧卡片 # 技巧1:哨兵技巧 — 简化边界处理heightsheights[0]# 末尾加 0 确保所有元素出栈# 技巧2:栈的非空判断leftstack[-1]ifstackelse-1# 栈空时左边界为 -1# 技巧3:enumerate 同时获取索引和值fori,hinenumerate(heights):# i 是索引,h 是值# 技巧4:单行条件表达式widthiifnotstackelsei-stack[-1]-1 底层原理(选读)为什么单调栈能高效找到左右边界?单调栈维护的是一个未来可能有用的候选集合。当遇到更小元素时:栈顶元素的右边界确定(就是当前元素)栈中前一个元素就是左边界(因为栈单调递增,前一个一定比当前小)出栈后,栈中剩余元素仍保持单调性,可继续使用为什么每个元素只会入栈/出栈一次?每个元素遍历到时入栈一次只有在遇到更小元素时才出栈,出栈后不会再入栈所以总操作数 2n,时间复杂度 O(n)算法模式卡片 模式名称:单调栈适用条件:需要找每个元素左/右第一个更大/更小的元素需要在线性时间内处理柱状图、温度等相邻关系问题识别关键词:“下一个更大/更小”“柱状图”“直方图”“每个元素向左/右能延伸多远”模板代码:defmonotonic_stack_template(arr):stack[]# 存索引result[]fori,valinenumerate(arr):# 维护单调性:递增栈用 ,递减栈用 whilestackandvalarr[stack[-1]]:idxstack.pop()# 在这里处理弹出元素(已找到右边界)leftstack[-1]ifstackelse-1# 计算区间 [left1, i-1]stack.append(i)# 处理栈中剩余元素(如果需要)returnresult易错点 ⚠️栈中存值还是存索引?❌ 错误:存值无法计算宽度✅ 正确:存索引,计算面积时width right - left - 1左边界怎么算?❌ 错误:left stack[-1](忘记检查栈空)✅ 正确:left stack[-1] if stack else -1是否需要哨兵?❌ 错误:不加哨兵,导致栈中剩余元素未处理✅ 正确:末尾加 0 哨兵,确保所有元素出栈单调栈的方向?❌ 错误:这题要用单调递减栈✅ 正确:要用单调递增栈,因为要找更小的元素作为边界️ 工程实战(选读)这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1:图像处理— 在二值图像中检测最大矩形区域(如 OCR 预处理)场景2:仓库优化— 在不同高度的货架中找最大可用存储空间场景3:数据可视化— 柱状图中自动标注最大矩形辅助分析场景4:建筑设计— 在不规则建筑群中规划最大矩形广场️ 举一反三完成本课后,试试这些同类题目来巩固知识:题目难度相关知识点提示LeetCode 85. 最大矩形Hard单调栈逐行转化将二维矩阵每一行转化为直方图,复用本题解法LeetCode 42. 接雨水Hard单调栈/双指针与本题类似,找左右边界,但计算方式不同LeetCode 739. 每日温度Medium单调栈单调栈基础题,找下一个更大元素LeetCode 496. 下一个更大元素 IEasy单调栈单调栈入门,理解栈的单调性维护 课后小测试试这道变体题,不要看答案,自己先想 5 分钟!题目:给定一个 0-1 矩阵,找出其中最大的矩形(全 1 区域)。例如:matrix [ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ] 最大矩形面积 6(从第 2 行到第 3 行,列 2-4) 提示(实在想不出来再点开)将每一行看作直方图的底,高度为从当前行往上连续 1 的个数。对每一行应用本课的单调栈解法。✅ 参考答案defmaximal_rectangle(matrix:List[List[str]])-int: 思路:逐行转化为柱状图最大矩形 ifnotmatrixornotmatrix[0]:return0rows,colslen(matrix),len(matrix[0])heights[0]*cols max_area0forrowinmatrix:# 更新当前行的直方图高度forjinrange(cols):ifrow[j]1:heights[j]1else:heights[j]0# 对当前直方图应用单调栈求最大矩形max_areamax(max_area,largest_rectangle_area(heights))returnmax_area核心思路:维护一个 heights 数组,记录每列从当前行往上连续 1 的个数遍历每一行,更新 heights,然后调用本课的largest_rectangle_area函数时间复杂度 O(m×n),m 是行数,n 是列数如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。