如何使用单调栈优化 Python 代码的时间复杂度
作者:WarmHope
时间:2025-09-17
来源:互联网
浏览:0
本文旨在指导读者如何使用单调栈这一数据结构,将原本时间复杂度为O(n²)的Python代码优化至O(n)。通过具体示例和详细解释,我们将展示如何利用单调栈高效地找到数组中每个元素的下一个更大元素,从而提升算法性能。

代码解释
- encoded = a[:] 创建了输入数组 a 的一个副本,这样修改 encoded 不会影响原始数组。
- s = [] 初始化了单调栈。
- enumerate(a) 用于同时获取数组的索引和值。
- while s and x > a[s[-1]] 循环确保栈的单调性。当遇到比栈顶元素更大的元素时,不断弹出栈顶元素,直到栈为空或者栈顶元素大于等于当前元素。
- encoded[s.pop()] += x 将栈顶元素对应的值更新为与当前元素的和。
- s.append(i) 将当前元素的索引压入栈中。
复杂度分析
- 时间复杂度: O(n)。虽然代码中包含一个 while 循环,但每个元素最多入栈一次,出栈一次,因此总的时间复杂度为 O(n)。
- 空间复杂度: O(n)。单调栈最多存储 n 个元素的索引。
注意事项
- 单调栈适用于解决寻找数组中下一个更大/更小元素的问题。
- 在实际应用中,可以根据具体需求选择单调递增栈或单调递减栈。
- 使用单调栈时,需要注意维护栈的单调性,确保算法的正确性。
总结
通过使用单调栈,我们可以将原本时间复杂度为 O(n²) 的代码优化至 O(n),显著提升算法的性能。单调栈是一种强大的数据结构,在解决与数组元素大小关系相关的问题时非常有用。理解单调栈的工作原理和应用场景,可以帮助我们编写更高效的 Python 代码。
作者最新文章
思源笔记
2026-09-16 17:42
在线PDF转TXT操作步骤与乱码排查指南
2026-09-04 13:02
PDF加水印后如何检查显示效果?在线工具操作步骤与避坑指南
2026-09-03 13:02
Xshell保持连接不断开及会话文件本地存储路径详解
2026-09-03 06:02
两个PDF怎么合并成一个?在线合并后怎么检查顺序?
2026-09-02 20:00
热门文章
更多
精品专题
更多
Mac软件
更多
WINDOWS
更多
Windows 10
Windows
Windows 10 是一款微软推出的经典操作系统,拥有硬件兼容性与多任务处理能力。它更偏向把系统状态查看和常用调节动作放在一起,适合需要持续观察和微调设备状态的场景。
极度公式
Windows/macOS/Linux
极度公式是一款跨平台专业LaTeX公式识别编辑软件,支持OCR公式识别和多平台编辑。和使用说明,避免使用,享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时,它能把识别后的处理步骤接得更顺,资料录入这类场景会省下不少时间。
















