单调栈与单调队列：优雅解决数组中的难题

🎯 学习目标

  • 掌握单调栈和单调队列的核心原理
  • 理解两种数据结构的实现方式与适用场景
  • 能够熟练应用单调栈/队列解决实际算法问题
  • 了解常见的优化技巧与经典应用

📑 目录

📁 核心概念

什么是单调数据结构？

单调数据结构是一种特殊的数据结构，其内部元素保持特定的单调性（递增或递减）。在算法问题中，单调数据结构常用于优化时间复杂度，特别是在处理数组中的next greater element、滑动窗口最大值等问题时表现出色。

最常见的单调数据结构有：

  • 单调栈：栈中元素保持单调递增或递减
  • 单调队列：队列中元素保持单调递增或递减

🚀 单调栈

🎯 核心思想

单调栈是一种特殊的栈，其中元素按照某种单调性（递增或递减）排列。它的关键特点是：每当新元素入栈时，会弹出栈中所有破坏单调性的元素，然后再入栈。

这种特性使得单调栈非常适合解决下一个更大元素、前一个更小元素等问题。

🎨 算法流程

以单调递减栈为例：

1
2
3
4
5
6
7
🚀 单调递减栈的基本操作：
1. 初始化一个空栈
2. 遍历数组中的每个元素：
   a. 当栈不为空且栈顶元素小于当前元素时，弹出栈顶元素
   b. 处理栈顶元素与当前元素的关系
   c. 将当前元素入栈
3. 处理栈中剩余的元素（可选）

💻 Java实现

1. 基础单调栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Stack;

/**
 * 🚀 单调栈的基础实现
 */
public class MonotonicStack {
    // 单调递减栈（栈顶元素为最大）
    public static void monotonicDecreasingStack(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 当栈不为空且栈顶元素小于当前元素时，弹出栈顶元素
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                // 此时nums[i]是栈顶元素的下一个更大元素
                int popped = stack.pop();
                System.out.println("元素 " + popped + " 的下一个更大元素是: " + nums[i]);
            }
            // 将当前元素入栈
            stack.push(nums[i]);
        }
        
        // 处理栈中剩余元素（没有下一个更大元素）
        while (!stack.isEmpty()) {
            int popped = stack.pop();
            System.out.println("元素 " + popped + " 没有下一个更大元素");
        }
    }
    
    // 单调递增栈（栈顶元素为最小）
    public static void monotonicIncreasingStack(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 当栈不为空且栈顶元素大于当前元素时，弹出栈顶元素
            while (!stack.isEmpty() && stack.peek() > nums[i]) {
                // 此时nums[i]是栈顶元素的下一个更小元素
                int popped = stack.pop();
                System.out.println("元素 " + popped + " 的下一个更小元素是: " + nums[i]);
            }
            // 将当前元素入栈
            stack.push(nums[i]);
        }
    }
}

2. 单调栈应用：下一个更大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 🚀 下一个更大元素问题（LeetCode 496）
 */
public class NextGreaterElement {
    /**
     * 计算数组中每个元素的下一个更大元素
     * 
     * @param nums 输入数组
     * @return 每个元素的下一个更大元素数组，没有则为-1
     */
    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // 初始化为-1，表示没有下一个更大元素
        Stack<Integer> stack = new Stack<>(); // 存储索引，而不是值
        
        for (int i = 0; i < n; i++) {
            // 当前元素大于栈顶索引对应的元素时，找到下一个更大元素
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                int index = stack.pop();
                result[index] = nums[i];
            }
            // 将当前索引入栈
            stack.push(i);
        }
        
        return result;
    }
}

🌊 单调队列

🎯 核心思想

单调队列是一种特殊的队列，其中元素按照某种单调性（递增或递减）排列。与单调栈不同，单调队列支持两端操作：在队尾添加元素，在队头移除元素。

单调队列常用于解决滑动窗口最大值/最小值等问题，可以将时间复杂度从O(nk)优化到O(n)。

🎨 算法流程

以单调递减队列（维护窗口最大值）为例：

1
2
3
4
5
6
7
8
🌊 单调递减队列处理滑动窗口最大值：
1. 初始化一个双端队列和结果数组
2. 遍历数组中的每个元素：
   a. 移除队列中所有小于当前元素的值（保持单调性）
   b. 将当前元素的索引加入队列
   c. 移除队列中超出窗口范围的元素（队头）
   d. 当窗口形成时，记录队头元素为当前窗口的最大值
3. 返回结果数组

💻 Java实现

1. 单调队列的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Deque;
import java.util.LinkedList;

/**
 * 🌊 单调队列的实现
 */
public class MonotonicQueue {
    // 双端队列，用于实现单调队列
    private Deque<Integer> deque = new LinkedList<>();
    
    // 入队操作，保持队列单调递减
    public void push(int value) {
        // 移除队列中所有小于当前元素的值
        while (!deque.isEmpty() && deque.peekLast() < value) {
            deque.pollLast();
        }
        // 将当前元素加入队列
        deque.offerLast(value);
    }
    
    // 出队操作（如果队头元素等于目标值）
    public void pop(int value) {
        if (!deque.isEmpty() && deque.peekFirst() == value) {
            deque.pollFirst();
        }
    }
    
    // 获取队列中的最大值（队头元素）
    public int max() {
        return deque.peekFirst();
    }
}

2. 单调队列应用：滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 🌊 滑动窗口最大值问题（LeetCode 239）
 */
public class SlidingWindowMaximum {
    /**
     * 计算滑动窗口中的最大值
     * 
     * @param nums 输入数组
     * @param k 窗口大小
     * @return 每个窗口的最大值组成的数组
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k == 0) return new int[0];
        
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // 存储索引
        
        for (int i = 0; i < n; i++) {
            // 1. 移除队列中超出窗口范围的元素（队头）
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 2. 移除队列中所有小于当前元素的值（保持单调性）
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // 3. 将当前索引加入队列
            deque.offerLast(i);
            
            // 4. 当窗口形成时，记录队头元素为当前窗口的最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

🔍 对比与选择策略

📊 核心区别对比表

特性 单调栈 单调队列
数据结构基础 栈 双端队列
操作方式 后进先出，仅一端操作 两端均可操作
单调性 递增或递减 递增或递减
典型应用 下一个更大/更小元素 滑动窗口最大值/最小值
时间复杂度 O(n) O(n)
空间复杂度 O(n) O(k)，k为窗口大小
优化场景 一维数组中的Next Greater问题 滑动窗口问题

🎯 选择策略

1
2
3
4
5
6
7
8
9
10
🤔 什么时候用单调栈？
✅ 需要找元素的下一个更大/更小元素
✅ 处理直方图相关问题
✅ 解决括号匹配、区间合并等问题
✅ 优化动态规划的状态转移

🤔 什么时候用单调队列？
✅ 需要处理滑动窗口最大值/最小值
✅ 维护动态的极值集合
✅ 需要在两端进行操作的场景

📋 单调栈对比总结

栈类型 单调性 弹出条件 解决的问题 遍历方向
递增栈 栈底 → 栈顶 ↑ 当前元素 ≤ 栈顶 右侧第一个更小元素 从右向左
递减栈 栈底 → 栈顶 ↓ 当前元素 ≥ 栈顶 右侧第一个更大元素 从右向左

💡 记忆技巧

单调性方向：

  • 递增栈 → 找更小元素（栈顶是最近的更小值）
  • 递减栈 → 找更大元素（栈顶是最近的更大值）

遍历方向：

  • 从右向左遍历时，栈中存储的是右侧的信息
  • 从左向右遍历时，栈中存储的是左侧的信息（需调整逻辑）

边界处理：

  • 栈为空时，表示无解（通常用 -1 或特殊值标记）

🏗️ 实战应用案例

🎯 案例1：柱状图中最大的矩形（LeetCode 84）

问题描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。

单调栈解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Stack;

/**
 * 📊 柱状图中最大的矩形（LeetCode 84）
 */
public class LargestRectangleInHistogram {
    /**
     * 计算柱状图中最大的矩形面积
     * 
     * @param heights 柱子高度数组
     * @return 最大矩形面积
     */
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        if (n == 0) return 0;
        
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        
        // 在数组末尾添加一个0，确保栈中所有元素都能被处理
        int[] extendedHeights = new int[n + 1];
        System.arraycopy(heights, 0, extendedHeights, 0, n);
        extendedHeights[n] = 0;
        
        for (int i = 0; i <= n; i++) {
            // 当前高度小于栈顶高度时，计算栈顶高度对应的矩形面积
            while (!stack.isEmpty() && extendedHeights[i] < extendedHeights[stack.peek()]) {
                int h = extendedHeights[stack.pop()]; // 当前柱子高度
                int w = stack.isEmpty() ? i : i - stack.peek() - 1; // 宽度
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

🎯 案例2：接雨水（LeetCode 42）

问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

单调栈解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Stack;

/**
 * 💧 接雨水问题（LeetCode 42）
 */
public class TrappingRainWater {
    /**
     * 计算能接的雨水总量
     * 
     * @param height 柱子高度数组
     * @return 能接的雨水总量
     */
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        
        Stack<Integer> stack = new Stack<>();
        int totalWater = 0;
        
        for (int i = 0; i < n; i++) {
            // 当前高度大于栈顶高度时，形成凹槽，可以接雨水
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = stack.pop(); // 凹槽底部位置
                
                if (stack.isEmpty()) break; // 没有左边界，无法接雨水
                
                int left = stack.peek(); // 左边界位置
                int width = i - left - 1; // 宽度
                int h = Math.min(height[left], height[i]) - height[bottom]; // 高度
                totalWater += width * h;
            }
            stack.push(i);
        }
        
        return totalWater;
    }
}

⚡ 性能分析

📊 时间复杂度对比

算法 朴素方法 使用单调数据结构 优化倍数
下一个更大元素 O(n²) O(n) n倍
滑动窗口最大值 O(nk) O(n) k倍
柱状图中最大矩形 O(n²) O(n) n倍
接雨水 O(n²) O(n) n倍

🚀 优化原理

单调数据结构的核心优化原理是：利用单调性避免不必要的比较。在处理数组问题时，很多情况下我们不需要与所有元素进行比较，只需要关注那些可能成为"下一个更大元素"或"窗口最大值"的元素。

通过维护单调的结构，我们可以在O(n)的时间复杂度内解决很多看似需要O(n²)时间的问题。

🎯 经典LeetCode题目

📝 基础题目（⭐⭐☆☆☆）

题号 题目名称 算法类型 难度
496 下一个更大元素 I 单调栈 ⭐⭐☆☆☆
503 下一个更大元素 II 单调栈 ⭐⭐☆☆☆
239 滑动窗口最大值 单调队列 ⭐⭐⭐☆☆
844 比较含退格的字符串 单调栈 ⭐⭐☆☆☆

📝 进阶题目（⭐⭐⭐☆☆）

题号 题目名称 算法类型 难度
84 柱状图中最大的矩形 单调栈 ⭐⭐⭐☆☆
42 接雨水 单调栈 ⭐⭐⭐☆☆
901 股票价格跨度 单调栈 ⭐⭐⭐☆☆
739 每日温度 单调栈 ⭐⭐⭐☆☆

📝 高难度题目（⭐⭐⭐⭐☆）

题号 题目名称 算法类型 难度
316 去除重复字母 单调栈 + 贪心 ⭐⭐⭐⭐☆
402 移掉K位数字 单调栈 + 贪心 ⭐⭐⭐⭐☆
85 最大矩形 单调栈 ⭐⭐⭐⭐☆
239 滑动窗口最大值（hard版） 单调队列 ⭐⭐⭐⭐☆

🧠 记忆口诀与技巧

🎯 单调栈记忆口诀

1
2
3
4
5
6
7
8
🚀 单调栈四步走：
1️⃣ 维护栈的单调性（弹出破坏规则的元素）
2️⃣ 处理弹出元素的关系（找到next greater/smaller）
3️⃣ 当前元素入栈（保持结构）
4️⃣ 清理栈中剩余元素（可选）

💡 单调栈精髓：
"后进先出保单调，遇到破坏就弹出，利用特性找关系，时间复杂降为O(n)"

🎯 单调队列记忆口诀

1
2
3
4
5
6
7
8
🌊 单调队列四步曲：
1️⃣ 清理过期元素（队头超出窗口）
2️⃣ 维护队列单调性（弹出队尾小于当前的元素）
3️⃣ 当前元素入队（从队尾）
4️⃣ 记录窗口极值（队头元素）

💡 单调队列精髓：
"双端操作维护单调，滑动窗口极值显，队头永远是最优，O(n)时间效率高"

🎓 学习总结

🎯 核心要点回顾

  1. 单调栈是解决 next greater/smaller 元素问题的利器，时间复杂度O(n)
  2. 单调队列特别适合处理滑动窗口最大值/最小值问题，同样O(n)时间复杂度
  3. 两种数据结构都通过维护单调性来避免不必要的比较，优化算法效率
  4. 实现时需要注意栈/队列中存储的是元素值还是索引，这取决于具体问题

🚀 进阶学习路线

  1. 📚 基础巩固：熟练掌握单调栈和单调队列的基本模板
  2. ⚡ 技巧提升：学习结合贪心、动态规划等算法的综合应用
  3. 🏗️ 实战应用：解决更多LeetCode相关题目，培养算法直觉
  4. 🔬 算法扩展：了解更复杂的数据结构，如单调堆、线段树等

💡 学习建议

1
2
3
4
5
📝 建议1：多画图理解单调数据结构的工作原理
📝 建议2：总结经典问题的模板代码，做到融会贯通
📝 建议3：通过练习不同难度的题目，深化对算法的理解
📝 建议4：注意分析问题特性，选择合适的单调数据结构
📝 建议5：关注边界条件的处理，避免出现数组越界等问题

最后更新：2025-01-16
作者：算法学习小分队