直方图最大面积问题适合用单调栈,因为每个柱子左右扩展宽度取决于两侧首个更矮柱子位置,单调栈可在O(n)内求出所有左右边界,而暴力法需O(n²)。

为什么直方图最大面积问题适合用单调栈
因为每个柱子能向左右扩展的宽度,取决于它两侧第一个比它矮的柱子位置——这正是单调栈擅长捕获的“最近更小元素”关系。暴力法要对每个柱子都往两边扫,时间复杂度是 O(n²);而单调栈只需一次遍历,O(n) 就能拿到所有柱子对应的左右边界。
如何用单调递增栈维护左边界和右边界
核心思路是:栈中存下标,保证栈内对应高度严格递增。当遇到 heights[i] 小于栈顶时,说明栈顶柱子的右边界就是 i,而左边界就是栈中它下面那个下标(即新栈顶)。
- 初始化栈为
[-1],方便处理第一个有效下标作为左边界 - 遍历
heights,对每个i:- 若
heights[i] ,持续弹出栈顶h_idx,计算以heights[h_idx]为高的矩形面积:heights[h_idx] * (i - stack[-1] - 1) - 最后把
i压入栈
- 若
- 遍历完后,栈中还剩递增序列,需额外处理:依次弹出,右边界设为
n(数组长度),左边界仍是栈中新栈顶
示例片段(关键逻辑):
stack = [-1]
max_area = 0
for i in range(n):
while stack[-1] != -1 and heights[i] <h3>容易忽略的边界细节和错误现象</h3><p>常见报错或结果偏小,往往卡在这几个点:</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill13660" title="使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中"><img
src="https://img.php.cn/upload/skill/001/246/273/6adaf20dee630206.jpg" alt="使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill13660" title="使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中" class="overflowclass">使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中</a>
<p class="overflowclass">当现有的脚本或服务需要将作用域化的仓库工作委托给 Claude Code 并以编程方式消费结构化响应时,请使用 Claude Agent SDK for Python。</p>
</div>
<a rel="nofollow" href="/xiazai/skill13660" title="使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
-
IndexError: list index out of range:没判stack[-1] != -1就直接取heights[stack[-1]],弹空后还访问栈顶 - 面积算错:宽度公式写成
i - stack[-1]或i - h_idx,漏减1;正确是i - stack[-1] - 1(两个边界都不包含) - 没处理尾部剩余栈元素:比如输入
[2,1,2],遍历完栈里剩[-1, 1, 2],不清理就会漏掉以heights[2]为高的矩形 - 栈中存值而非下标:会导致无法计算宽度,也丢失原始位置信息
Python 实现中栈操作与性能注意事项
Python 的 list 用作栈完全可行,append() 和 pop() 都是 O(1) 均摊。但要注意:
- 避免用
stack.pop(0)或stack.insert(0, ...),那是模拟队列,会触发整体搬移,退化成O(n) - 不要在循环中反复调用
len(stack),虽然影响小,但可直接用stack[-1] != -1替代判空 - 如果输入规模极大(如百万级),考虑用
collections.deque,但对单调栈场景实际提升微乎其微
真正影响性能的是逻辑分支是否精简,而不是容器类型选择。
栈空判断、宽度计算、尾部清栈——这三个地方写错一个,答案就错。尤其宽度公式,手写两遍都可能漏掉那个 -1。
Python免费学习笔记(深入):立即使用
在学习笔记中,你将探索 Python 的核心概念和高级技巧!










