LeetCode的单调栈与单调队列
单调栈与单调队列：算法世界中的秩序维护者
在算法设计与优化的领域中，单调栈与单调队列是两种精妙而强大的数据结构。它们并非标准库中的现成组件，而是基于基础数据结构演化而来的解题思想。这两种结构以其独特的“单调性”维护机制，在特定类型问题中展现出惊人的效率提升。
单调栈：维护序列的单调秩序
单调栈的核心思想是在处理序列时，维护一个栈内元素保持单调递增或递减的顺序。当新元素到来时，通过弹出破坏单调性的元素，确保栈内秩序始终如一。
工作原理与实现
单调栈的典型操作模式如下：遍历数组中的每个元素，当栈不为空且当前元素与栈顶元素的关系破坏所需的单调性时，弹出栈顶元素。这个弹出的过程往往正是解决问题的关键时刻——我们可以计算被弹出元素与当前元素及栈中下一个元素之间的关系。
以经典的“每日温度”问题为例，我们需要找到每一天之后需要等待多少天才能有更高的温度。单调递减栈的解决方案优雅而高效：
```python
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] n
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result
```
在这个实现中，栈中存储的是索引而非温度值本身。当遇到更高温度时，我们就能计算出之前那些较低温度需要等待的天数。
应用场景分析
单调栈最擅长解决的是一类“下一个更大/更小元素”问题。例如在“柱状图中最大的矩形”问题中，我们需要找到每个柱子左右两边第一个低于它的柱子，这两个柱子之间的区域就是以该柱子为高的最大矩形宽度。单调递增栈在这里发挥了关键作用：
```python
def largestRectangleArea(heights):
heights.append(0) 哨兵元素
stack = [-1] 哨兵索引
max_area = 0
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
max_area = max(max_area, h w)
stack.append(i)
heights.pop() 恢复原数组
return max_area
```
这里的哨兵技巧值得注意：通过在数组末尾添加0，并在栈底放置-1，我们确保了所有柱子都能被正确处理，无需额外的边界检查。
单调队列：滑动窗口的优化利器
如果说单调栈擅长处理静态序列中的关系问题，那么单调队列则是滑动窗口类问题的天然解决方案。单调队列能够在O(1)时间内获取窗口中的最大值或最小值，这是普通队列无法做到的。
数据结构特性
单调队列通常使用双端队列实现，允许在两端进行插入和删除操作。维护单调性的关键在于：当新元素加入时，从队列尾部移除所有比它小（对于单调递减队列）或比它大（对于单调递增队列）的元素，确保队列的单调性不被破坏。
考虑“滑动窗口最大值”这一经典问题：
```python
def maxSlidingWindow(nums, k):
from collections import deque
result = []
deq = deque()
for i in range(len(nums)):
移除超出窗口范围的元素
if deq and deq[0] == i - k:
deq.popleft()
维护队列单调递减
while deq and nums[deq[-1]] < nums[i]:
deq.pop()
deq.append(i)
当窗口形成后记录结果
if i >= k - 1:
result.append(nums[deq[0]])
return result
```
这个实现中，队列存储的是索引而非值本身，这样既能通过值比较维护单调性，又能通过索引判断元素是否还在窗口内。
进阶应用：限制条件下的优化
单调队列的真正威力在于解决带有额外约束的问题。例如在“满足限制条件的子数组”类问题中，我们需要在维护窗口极值的同时，确保窗口内的某些属性满足特定条件。单调队列与其他算法的结合往往能产生奇效。
对比分析与选择策略
虽然单调栈和单调队列都维护单调性，但它们的应用场景有明显区别：
- 单调栈通常用于解决全局或单向问题，如寻找每个元素左右两侧的边界
- 单调队列专攻滑动窗口问题，需要在窗口移动时动态维护极值
选择使用哪种结构的关键在于分析问题的本质：如果问题涉及固定点与其邻居的关系，考虑单调栈；如果问题涉及滑动区间内的极值查询，考虑单调队列。
实战技巧与常见陷阱
掌握单调栈与单调队列不仅需要理解原理，还需要注意一些实践细节：
1. 索引与值的权衡：大多数情况下存储索引比存储值更有用，因为索引既能获取值，又能计算距离和判断位置关系。
2. 哨兵元素的妙用：在数组边界添加哨兵值（如0或inf）可以简化代码逻辑，避免繁琐的边界检查。
3. 相等元素的处理：根据具体问题决定相等时是否弹出元素。在“下一个更大元素”问题中，通常相等时不弹出；而在某些问题中可能需要特殊处理。
4. 空间复杂度考量：虽然两种结构都能在O(n)空间内解决问题，但在内存敏感的场景中，可以考虑是否能用变量替代显式栈/队列。
总结与展望
单调栈与单调队列体现了算法设计中一个深刻思想：通过维护数据结构的特定性质（单调性），我们可以将看似复杂的问题简化为线性时间的操作。这两种结构在LeetCode等算法平台中频繁出现，掌握它们不仅能帮助解决具体问题，更能培养一种优化思维——如何在数据处理过程中保持有益的结构性质。
随着算法问题形式的不断演化，单调栈与单调队列的变体和应用场景也在不断扩展。从简单的数组问题到复杂的流数据处理，从一维序列到二维矩阵，这两种结构的核心思想持续发挥着重要作用。对于算法学习者而言，深入理解并灵活运用单调栈与单调队列，无疑是提升解题能力的重要一步。
在算法的世界里，秩序往往意味着效率。单调栈与单调队列正是这种秩序的维护者，它们以简洁而强大的方式，在数据的洪流中建立起可预测的模式，从而让我们能够高效地解决那些原本复杂的问题。