单调栈详解：从入门到实践

背景介绍

在计算机科学中，我们经常需要解决”找到数组中下一个更大/更小元素”、”寻找数组中的模式”等问题。传统的方法可能需要嵌套循环，时间复杂度达到O(n²)。单调栈的出现为这类问题提供了一个优雅且高效的解决方案。

基本概念

什么是单调栈？

单调栈是一种特殊的栈结构，其中的元素保持单调递增或单调递减的顺序。与普通栈相比，单调栈在插入新元素时会维护这种单调性，必要时会弹出栈顶元素。

想象一下排队买票的场景：

• 如果要求按身高从矮到高排队（单调递增），当一个高个子来了后发现前面有比他高的，那些人就要让出位置
• 如果要求按身高从高到矮排队（单调递减），当一个矮个子来了后发现前面有比他矮的，那些人就要让出位置

单调栈的类型

1. 单调递增栈
   • 从栈底到栈顶元素单调递增（栈顶最大）
   • 用于找下一个更小的元素
   • 特点：保证栈内元素始终是从小到大排列
2. 单调递减栈
   • 从栈底到栈顶元素单调递减（栈顶最小）
   • 用于找下一个更大的元素
   • 特点：保证栈内元素始终是从大到小排列

工作原理

让我们通过一个生动的例子来理解单调栈的工作原理：

单调递增栈的工作流程

以数组 [5, 2, 8, 3, 7] 为例，我们要构建一个单调递增栈：

初始状态：[]
1. 遇到 5：
   栈：[5]
   
2. 遇到 2：
   由于 2 < 5，5出栈
   栈：[2]
   
3. 遇到 8：
   由于 8 > 2，直接入栈
   栈：[2, 8]
   
4. 遇到 3：
   由于 3 < 8，8出栈
   栈：[2, 3]
   
5. 遇到 7：
   由于 7 > 3，直接入栈
   栈：[2, 3, 7]

最终栈内元素：[2, 3, 7]（保持递增）

单调递减栈的工作流程

同样以数组 [5, 2, 8, 3, 7] 为例：

初始状态：[]
1. 遇到 5：
   栈：[5]
   
2. 遇到 2：
   由于 2 < 5，直接入栈
   栈：[5, 2]
   
3. 遇到 8：
   由于 8 > 2 且 8 > 5，2和5都出栈
   栈：[8]
   
4. 遇到 3：
   由于 3 < 8，直接入栈
   栈：[8, 3]
   
5. 遇到 7：
   由于 7 > 3，3出栈
   由于 7 < 8，7入栈
   栈：[8, 7]

最终栈内元素：[8, 7]（保持递减）

实际应用示例

1. 股票价格跨度问题

这是一个来自股票交易领域的实际问题：

想象你是一个股票分析师，需要回答这样的问题： “今天的股票价格连续多少天是历史最高的？”或者说 “向前看，连续多少天的股价都不超过今天的价格？”

举个例子：

股票价格序列：[100, 80, 60, 70, 60, 75, 85]
                ↓   ↓   ↓   ↓   ↓   ↓   ↓
跨度值：         1   1   1   2   1   4   6

解释：
- 100元时，只有当天，跨度为1
- 80元时，比100小，跨度为1
- 60元时，比80小，跨度为1
- 70元时，比60和70都大，跨度为2
- 60元时，比70小，跨度为1
- 75元时，比前面4天都大，跨度为4
- 85元时，比前面6天都大，跨度为6

使用单调栈的解决方案：

class StockSpanner {
    // 存储（价格，跨度）对
    private var stack: [(price: Int, span: Int)] = []
    
    func next(_ price: Int) -> Int {
        var span = 1 // 至少包含今天
        
        // 当栈不为空且栈顶价格小于等于当前价格时
        while let last = stack.last, last.price <= price {
            span += last.span // 累加跨度
            stack.removeLast()
        }
        
        stack.append((price, span))
        return span
    }
}

// 使用示例
let spanner = StockSpanner()
print(spanner.next(100)) // 1 (第一天)
print(spanner.next(80))  // 1 (小于前一天)
print(spanner.next(60))  // 1 (小于前一天)
print(spanner.next(70))  // 2 (大于前一天的60)
print(spanner.next(60))  // 1 (小于前一天)
print(spanner.next(75))  // 4 (大于前面的60,70,60)
print(spanner.next(85))  // 6 (大于前面除了100的所有价格)

2. 接雨水问题

这是一个经典的问题，可以类比成现实生活中的情景： 想象有一排不同高度的墙，下雨后，这些墙之间能积攒多少雨水？

关键思路：

1. 水能够积攒的前提是形成”凹槽”
2. 凹槽需要左右两边有更高的墙
3. 水的高度取决于两边较矮的那堵墙

以一个简单的例子来说明：

地形：[2,0,2]
形状：█ █
     █_█
结果：2 (中间可以装2个单位的水)

更复杂的例子 [0,1,0,2,1,0,1,3,2,1,2,1]：

初始地形：
     3
     █
 2   █ █  █
 █ █ ██████
 ████████████
 012345678901

下雨后：
     3
     █
 2   █ █  █
 █ █ ██████
 ████████████
   ~ ~  ~     (~ 表示积水)

使用单调栈的解决方案：

func trap(_ height: [Int]) -> Int {
    var stack: [(index: Int, height: Int)] = []
    var water = 0
    
    for (i, h) in height.enumerated() {
        // 当遇到一个较高的墙时，可能形成凹槽
        while let last = stack.last, h >= last.height {
            let bottom = stack.removeLast() // 凹槽的底部
            
            // 如果栈空了，说明左边没有墙，无法形成凹槽
            if let left = stack.last {
                let width = i - left.index - 1  // 凹槽的宽度
                let height = min(left.height, h) - bottom.height // 凹槽可以存水的高度
                water += width * height // 这个凹槽能存的水量
            }
        }
        stack.append((i, h))
    }
    
    return water
}

// 使用示例
let heights = [2,0,2]
print("简单情况能接住的水量：\(trap(heights))") // 输出：2

let complexHeights = [0,1,0,2,1,0,1,3,2,1,2,1]
print("复杂情况能接住的水量：\(trap(complexHeights))") // 输出：6

3. 每日温度问题

这是一个来自气象预报的实际问题： 如果你是一个气象预报员，人们总是问你： “还要等多少天才能遇到一个更暖和的天气？”

举个生活中的例子：

一周温度变化：[23, 24, 25, 21, 19, 22, 26]
                ↓   ↓   ↓   ↓   ↓   ↓   ↓
等待天数：      1   1   4   2   1   1   0

解释：
- 23度时，第2天就遇到24度，等待1天
- 24度时，第3天就遇到25度，等待1天
- 25度时，要等到第7天才遇到26度，等待4天
- 21度时，要等到第6天遇到22度，等待2天
- 19度时，第6天遇到22度，等待1天
- 22度时，第7天遇到26度，等待1天
- 26度时，后面没有更高温度了，等待0天

使用单调栈的解决方案：

func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    var result = Array(repeating: 0, count: temperatures.count)
    var stack: [(day: Int, temp: Int)] = []
    
    for (today, temp) in temperatures.enumerated() {
        // 当发现更暖和的温度时
        while let last = stack.last, temp > last.temp {
            let prevDay = stack.removeLast().day
            result[prevDay] = today - prevDay // 计算等待天数
        }
        stack.append((today, temp))
    }
    
    return result
}

// 使用示例
let temperatures = [23, 24, 25, 21, 19, 22, 26]
let result = dailyTemperatures(temperatures)
print("每天需要等待的天数：\(result)") // [1, 1, 4, 2, 1, 1, 0]

/*
温度变化图：
26 |           █
25 |     █     
24 |   █       
23 | █         
22 |         █ 
21 |       █   
20 |           
19 |         █ 
   +-----------
     1 2 3 4 5 6 7
*/

这三个例子展示了单调栈在不同场景下的应用：

1. 股票价格跨度：寻找连续的历史最高值
2. 接雨水：寻找凹槽并计算容量
3. 温度预测：寻找下一个更高的值

它们的共同点是：

• 都需要找到下一个更大/更小的元素
• 都可以通过维护一个单调栈来高效解决
• 都避免了传统的O(n²)暴力解法

性能优化技巧

1. 预分配容量

// 预先分配栈的容量，避免频繁扩容
var stack = ContiguousArray<Int>()
stack.reserveCapacity(expectedSize)

2. 使用值类型优化

// 使用结构体替代元组，提高可读性和性能
struct StackElement: Comparable {
    let index: Int
    let value: Int
    
    static func < (lhs: StackElement, rhs: StackElement) -> Bool {
        lhs.value < rhs.value
    }
}

3. 内存优化

// 使用小内存占用的数据结构
struct CompactStackElement {
    // 使用较小的整数类型
    let index: Int16
    let value: Int16
}

使用建议

1. 选择合适的单调性
   • 找下一个更大元素 → 使用单调递减栈
   • 找下一个更小元素 → 使用单调递增栈
2. 处理边界情况
   • 栈为空时的处理
   • 数组末尾元素的处理
   • 相等元素的处理策略
3. 调试技巧
   • 使用小规模测试用例
   • 打印栈的变化过程
   • 可视化栈的状态

总结

单调栈是一个既简单又强大的数据结构，它通过维护栈的单调性来高效解决特定类型的问题。关键要点：

1. 理解单调性的概念和维护方式
2. 掌握不同类型单调栈的应用场景
3. 熟练运用在实际问题中
4. 注意性能优化和边界处理

通过本文的学习，你应该能够：

• 理解单调栈的工作原理
• 实现基本的单调栈结构
• 运用单调栈解决实际问题
• 优化单调栈的实现

练习建议

1. LeetCode相关题目：
   • #739 每日温度
   • #42 接雨水
   • #84 柱状图中最大的矩形
   • #901 股票价格跨度
   • #496 下一个更大元素 I
2. 进阶练习：
   • 尝试实现循环数组中的下一个更大元素
   • 解决带有重复元素的问题
   • 优化空间复杂度

参考资源

1. LeetCode相关题目集合
2. 数据结构与算法教程
3. Swift官方文档
4. 算法可视化网站

希望这篇详细的教程能帮助你更好地理解和使用单调栈这一数据结构。记住，实践是掌握算法的最好方式！