1. 单调栈基础概念解析单调栈Monotonic Stack是一种特殊的栈结构它在算法题解中经常用于处理下一个更大/更小元素这类问题。我第一次接触这个概念是在解决LeetCode第496题下一个更大元素I时当时用暴力解法O(n²)总超时直到发现这个神奇的数据结构。单调栈的核心特性是栈内元素始终保持单调递增或单调递减的顺序。这种特性使得它能够在O(n)时间复杂度内解决许多看似复杂的问题。举个例子就像排队买奶茶时店员总是优先服务最后来的顾客栈顶元素但如果新来的顾客比前面的人优先级高数值更大或更小就会打破原有的排队顺序。2. 单调栈的两种基本类型2.1 单调递增栈单调递增栈要求栈内元素从栈底到栈顶保持严格递增。当新元素准备入栈时需要弹出所有比它大的栈顶元素直到满足递增条件。这种结构特别适合解决寻找下一个更小元素的问题。def increasing_stack(nums): stack [] for num in nums: while stack and stack[-1] num: stack.pop() stack.append(num) return stack2.2 单调递减栈单调递减栈则相反要求栈内元素从栈底到栈顶保持严格递减。它常用于解决寻找下一个更大元素的问题。我在解决LeetCode第739题每日温度时就使用了这种结构。def decreasing_stack(nums): stack [] for num in nums: while stack and stack[-1] num: stack.pop() stack.append(num) return stack3. 单调栈的典型应用场景3.1 下一个更大/更小元素问题这是单调栈最经典的应用场景。以LeetCode第503题下一个更大元素II为例我们需要在循环数组中找到每个元素的下一个更大元素。使用单调递减栈可以在O(n)时间内解决这个问题。def nextGreaterElements(nums): n len(nums) res [-1] * n stack [] for i in range(2 * n): while stack and nums[stack[-1]] nums[i % n]: res[stack.pop()] nums[i % n] if i n: stack.append(i) return res3.2 柱状图最大矩形面积LeetCode第84题柱状图中最大的矩形是另一个经典应用。这个问题需要找到柱状图中面积最大的矩形使用单调递增栈可以高效解决。def largestRectangleArea(heights): heights.append(0) # 哨兵节点 stack [-1] max_area 0 for i in range(len(heights)): while stack[-1] ! -1 and heights[stack[-1]] heights[i]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area4. 单调栈的实现技巧与注意事项4.1 边界处理技巧在实际编码中边界条件往往是出错的重灾区。我总结了几个常见处理技巧哨兵节点在数组开头或结尾添加特殊值简化逻辑循环数组通过取模运算处理循环情况空栈判断每次访问栈顶前检查栈是否为空4.2 时间复杂度分析虽然单调栈有嵌套循环但每个元素最多入栈和出栈各一次因此时间复杂度是O(n)而非O(n²)。这点在面试时需要能够清晰解释。4.3 常见错误与调试方法新手常犯的错误包括忘记处理栈为空的情况混淆递增栈和递减栈的应用场景在计算宽度时使用了错误的索引调试时可以打印出每一步的栈状态和中间结果这是我在初学时的有效方法。5. 单调栈的进阶应用5.1 二维矩阵中的问题单调栈不仅可以解决一维数组问题还能扩展到二维场景。比如LeetCode第85题最大矩形需要将问题转化为多个柱状图最大矩形问题来解决。5.2 与其他数据结构的结合在实际工程中单调栈常与哈希表、优先队列等数据结构结合使用。例如在解决下一个更大元素I时可以用哈希表记录元素映射关系。5.3 实际工程应用虽然单调栈在算法题中很常见但在实际工程中也有广泛应用比如编译器中的语法分析网络数据包的处理股票交易系统中的价格分析6. 单调栈的变种与扩展6.1 单调队列单调队列是单调栈的扩展可以在两端操作。它适合解决滑动窗口最值问题如LeetCode第239题滑动窗口最大值。6.2 带权值的单调栈在某些问题中元素可能带有额外权值。这时需要调整单调栈的实现在弹出元素时同时处理权值信息。6.3 多维度单调性更复杂的问题可能需要同时考虑多个维度的单调性这时可以结合多个单调栈或使用更高级的数据结构。