单调栈

本章目标：掌握单调栈模板，解决"下一个更大元素"和"柱状图最大矩形"等经典问题。

你将学到

• 单调递增栈与单调递减栈
• "下一个更大/更小元素"模板
• 接雨水的单调栈解法
• 柱状图中最大矩形
• 循环数组处理

1. 概念

单调栈是一种特殊的栈，维护栈内元素的单调性（递增或递减）。它的核心应用是在 O(n) 时间内找到每个元素左边/右边第一个比它大/小的元素。

暴力方法对每个元素向左/右扫描是 O(n²)，单调栈通过维护一个递增（或递减）序列，每个元素最多入栈出栈各一次，降为 O(n)。

规则：

• 找下一个更大元素 → 单调递减栈（栈底到栈顶递减）
• 找下一个更小元素 → 单调递增栈（栈底到栈顶递增）

当新元素打破栈的单调性时，弹出栈顶元素——此时新元素就是被弹元素右侧第一个更大的元素。

2. 核心模板

下一个更大元素

/// 返回每个元素右侧第一个比它大的元素值（没有则为 -1）
func nextGreaterElement(_ nums: [Int]) -> [Int] {
    let n = nums.count
    var result = [Int](repeating: -1, count: n)
    var stack: [Int] = []  // 存索引，对应值单调递减

    for i in 0..<n {
        while let top = stack.last, nums[top] < nums[i] {
            result[top] = nums[i]  // nums[i] 是 nums[top] 的下一个更大元素
            stack.removeLast()
        }
        stack.append(i)
    }
    return result
}

复杂度

• 时间：O(n)，每个元素最多入栈出栈各一次
• 空间：O(n)

3. 经典题目精讲

LeetCode 739 · 每日温度

题意：给定每日温度，对每天计算还要等几天才能出现更高温度。

思路：单调递减栈存索引，弹出时计算天数差。

func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    let n = temperatures.count
    var result = [Int](repeating: 0, count: n)
    var stack: [Int] = []  // 存索引，温度单调递减

    for i in 0..<n {
        while let top = stack.last, temperatures[top] < temperatures[i] {
            result[top] = i - top
            stack.removeLast()
        }
        stack.append(i)
    }
    return result
}

LeetCode 42 · 接雨水（单调栈解法）

题意：给定柱子高度，求接住的雨水量。

思路：单调递减栈，当遇到更高的柱子时弹出栈顶形成凹槽，按层计算水量。

func trap(_ height: [Int]) -> Int {
    var stack: [Int] = []  // 存索引，高度单调递减
    var water = 0
    for i in 0..<height.count {
        while let top = stack.last, height[top] < height[i] {
            let bottom = stack.removeLast()  // 凹槽底部
            guard let left = stack.last else { break }  // 凹槽左壁
            let width = i - left - 1
            let h = min(height[left], height[i]) - height[bottom]
            water += width * h
        }
        stack.append(i)
    }
    return water
}

LeetCode 84 · 柱状图中最大矩形

题意：给定柱状图各柱高度，找最大矩形面积。

思路：单调递增栈，对每根柱子找左边和右边第一个比它矮的位置，计算以该柱为高的矩形面积。

func largestRectangleArea(_ heights: [Int]) -> Int {
    var stack: [Int] = []  // 存索引，高度单调递增
    var maxArea = 0
    // 遍历到 n 是为了处理剩余元素
    for i in 0...heights.count {
        let curHeight = i < heights.count ? heights[i] : 0
        while let top = stack.last, heights[top] > curHeight {
            let h = heights[stack.removeLast()]
            let w = stack.isEmpty ? i : i - stack.last! - 1
            maxArea = max(maxArea, h * w)
        }
        if i < heights.count {
            stack.append(i)
        }
    }
    return maxArea
}

LeetCode 503 · 下一个更大元素 II（循环数组）

思路：遍历两圈即可，通过取模访问。

func nextGreaterElements(_ nums: [Int]) -> [Int] {
    let n = nums.count
    var result = [Int](repeating: -1, count: n)
    var stack: [Int] = []
    for i in 0..<(2 * n) {
        let idx = i % n
        while let top = stack.last, nums[top] < nums[idx] {
            result[top] = nums[idx]
            stack.removeLast()
        }
        if i < n { stack.append(idx) }
    }
    return result
}

4. 易错点

• ⚠️ 栈存索引还是值——通常存索引，因为需要计算距离/宽度
• ⚠️ 循环数组遍历两圈时，第二圈不再入栈
• ⚠️ 柱状图问题需要在末尾加哨兵元素（高度为 0）来弹完所有元素
• ⚠️ 接雨水单调栈解法中，弹出后栈为空说明左边没有壁，不能接水

5. 推荐刷题清单

题号	题名	难度	关键
42	接雨水	Hard	单调栈/双指针
84	柱状图中最大矩形	Hard	单调递增栈
496	下一个更大元素 I	Easy	模板题
503	下一个更大元素 II	Medium	循环数组
739	每日温度	Medium	模板题

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)