给定一个长度为100万的数组，要求找出每个元素右侧第一个比它大的元素。最直观的做法是：对每个元素，向右扫描直到找到更大的元素。最坏情况下，每个元素都需要扫描到数组末尾——总的时间复杂度是$O(n^2)$。

但如果换一种思路：用栈维护一个单调递减的序列，每个元素入栈时，弹出所有比它小的元素——这些被弹出的元素恰好找到了它们的"下一个更大元素"。这样每个元素最多入栈一次、出栈一次，时间复杂度直接降到$O(n)$。

这就是单调栈算法的核心魅力：通过维护栈内元素的单调性，将看似需要嵌套循环的问题优化为线性扫描。

单调栈的本质：有序的等待队列

单调栈（Monotonic Stack）是一种特殊的栈结构，其内部元素始终保持单调递增或单调递减的顺序。它不是一种独立的数据结构，而是栈的一种特殊使用方式——通过在入栈时主动弹出破坏单调性的元素，来维护栈的有序性。

理解单调栈的关键在于"等待"的概念。当元素入栈时，它可能在等待某个事件发生（比如遇到一个更大的元素）。栈中存储的是那些"尚未等到答案"的元素，而栈的单调性保证了我们能高效地为这些等待者找到答案。

具体来说，单调栈分为四种类型：

单调递增栈：栈底到栈顶元素依次增大。用于解决"下一个更小元素"问题。

单调递减栈：栈底到栈顶元素依次减小。用于解决"下一个更大元素"问题。

严格单调栈：不允许相等元素相邻，弹出时使用严格比较（< 或 >）。

非严格单调栈：允许相等元素相邻，弹出时使用非严格比较（<= 或 >=）。

问题类型 栈类型 while循环条件
下一个更大元素 单调递减（非严格） stackTop < current
前一个更大元素 单调递减（严格） stackTop <= current
下一个更小元素 单调递增（非严格） stackTop > current
前一个更小元素 单调递增（严格） stackTop >= current

这个对应关系存在一个有趣的规律：求"更大"需要递减栈，求"更小"需要递增栈。这与直觉相反，原因在于：当我们遇到一个更大的元素时，它可以成为栈中所有比它小的元素的"下一个更大元素"，因此需要弹出这些小元素——这自然形成了一个递减栈。

通用模板：从框架到实践

掌握了四种栈类型后，我们来看单调栈的通用代码模板。这个模板可以应对绝大多数单调栈问题：

public int[] monotonicStack(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);  // 初始化为无效值
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // while循环：弹出所有不满足单调性的元素
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int stackTop = stack.pop();
            // 在这里处理被弹出的元素
            result[stackTop] = nums[i];  // 或 result[stackTop] = i
        }
        
        // while循环结束后，栈顶元素就是当前元素的"前一个更大/更小元素"
        if (!stack.isEmpty()) {
            // 在这里处理当前元素的前驱关系
        }
        
        stack.push(i);  // 将当前索引入栈
    }
    
    return result;
}

这个模板的核心在于两个处理位置：

while循环内部：处理被弹出元素的"下一个"关系。比如在单调递减栈中，当前元素nums[i]就是被弹出元素nums[stackTop]的下一个更大元素。

while循环之后：处理当前元素的"前一个"关系。比如在单调递减栈中，栈顶元素（如果存在）就是当前元素的"前一个更大元素"。

下一个更大元素系列

LeetCode 496. Next Greater Element I

这是单调栈最基础的应用，直接考察"下一个更大元素"的计算。

题目描述：给定两个数组nums1和nums2，其中nums1是nums2的子集。对nums1中的每个元素，找出其在nums2中右侧第一个更大的元素。

示例：nums1 = [4,1,2], nums2 = [1,3,4,2]，输出[-1,3,-1]

解题思路：先用单调栈预处理nums2，建立每个元素到其下一个更大元素的映射，然后查询nums1中的元素。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 预处理：计算nums2中每个元素的下一个更大元素
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int num : nums2) {
            // 单调递减栈：弹出所有比当前元素小的元素
            while (!stack.isEmpty() && stack.peek() < num) {
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }
        
        // 栈中剩余元素没有下一个更大元素
        while (!stack.isEmpty()) {
            nextGreater.put(stack.pop(), -1);
        }
        
        // 查询nums1中每个元素的答案
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreater.get(nums1[i]);
        }
        return result;
    }
}

复杂度分析：时间复杂度$O(n)$，空间复杂度$O(n)$。

LeetCode 503. Next Greater Element II

这道题引入了"循环数组"的概念，需要处理数组首尾相连的情况。

题目描述：给定循环数组nums，返回每个元素的下一个更大元素。循环意味着数组的末尾后面是开头。

示例：nums = [1,2,1]，输出[2,-1,2]（最后一个1的下一个更大元素是开头的2）

解题思路：将数组"虚拟"延长一倍，或者将循环次数翻倍。关键是不真正复制数组，而是通过取模运算模拟。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 循环两遍，模拟循环数组
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            while (!stack.isEmpty() && nums[stack.peek()] < nums[idx]) {
                result[stack.pop()] = nums[idx];
            }
            // 只在第一遍循环时入栈
            if (i < n) {
                stack.push(idx);
            }
        }
        return result;
    }
}

关键点：第二遍循环时不再入栈，避免重复处理。这是因为第二遍只是为了给第一遍遗留的元素找答案。

LeetCode 739. Daily Temperatures

这道题是下一个更大元素问题的变种，要求返回"距离"而非"元素值"。

题目描述：给定每日温度数组，对每一天返回需要等待多少天才能遇到更高的温度。

示例：temperatures = [73,74,75,71,69,72,76,73]，输出[1,1,4,2,1,1,0,0]

解题思路：单调栈存储索引，答案就是两个索引的差值。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int prev = stack.pop();
                result[prev] = i - prev;  // 距离 = 当前索引 - 之前索引
            }
            stack.push(i);
        }
        // 栈中剩余元素的答案保持为0
        
        return result;
    }
}

接雨水：单调栈的经典应用

LeetCode 42. Trapping Rain Water

这道题是单调栈最具代表性的应用之一，也是面试高频难题。

题目描述：给定非负整数数组表示高度图，计算能接多少雨水。

示例：height = [0,1,0,2,1,0,1,3,2,1,2,1]，输出6

解题思路：

接雨水的关键在于：对于每个位置，它能接的雨水量取决于它左右两侧最高的柱子中的较低者。用单调栈的角度看：当遇到一个比栈顶高的柱子时，栈顶位置可能可以接水——因为左边有更高的柱子（栈顶下面的元素），右边也有更高的柱子（当前元素）。

接雨水示意图

图片来源: GeeksforGeeks - Trapping Rain Water

class Solution {
    public int trap(int[] height) {
        int water = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < height.length; i++) {
            // 单调递增栈：当遇到更高的柱子时，计算雨水
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                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];  // 高度
                water += width * h;
            }
            stack.push(i);
        }
        
        return water;
    }
}

核心逻辑解析：

  1. 栈中存储的是"可能成为凹槽底部的位置"
  2. 当遇到更高的柱子height[i]时，弹出栈顶作为凹槽底部bottom
  3. 新的栈顶left是左边界，当前元素i是右边界
  4. 雨水高度 = min(左边界高度, 右边界高度) - 底部高度
  5. 雨水宽度 = 右边界索引 - 左边界索引 - 1

复杂度分析：时间复杂度$O(n)$，空间复杂度$O(n)$。

柱状图最大矩形：前后更小元素的完美结合

LeetCode 84. Largest Rectangle in Histogram

这道题展示了单调栈如何同时求"前一个更小"和"下一个更小"。

题目描述：给定柱状图的高度数组，求能勾勒出的最大矩形面积。

示例：heights = [2,1,5,6,2,3]，输出10

解题思路：

对于每个柱子，以它为高度的矩形能向左右延伸多远？答案是：向左延伸到第一个更矮的柱子右边，向右延伸到第一个更矮的柱子左边。因此，问题转化为求每个柱子的"前一个更小元素"和"下一个更小元素"。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] leftSmaller = new int[n];   // 前一个更小元素的索引
        int[] rightSmaller = new int[n];  // 下一个更小元素的索引
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 同时计算前一个更小和下一个更小
        for (int i = 0; i < n; i++) {
            // 单调递增栈（严格）：弹出所有 >= 当前的元素
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                int top = stack.pop();
                rightSmaller[top] = i;  // 当前元素是弹出元素的下一个更小
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();  // 栈顶是前一个更小
            stack.push(i);
        }
        
        // 栈中剩余元素的下一个更小是数组末尾
        while (!stack.isEmpty()) {
            rightSmaller[stack.pop()] = n;
        }
        
        // 计算最大面积
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = rightSmaller[i] - leftSmaller[i] - 1;
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        
        return maxArea;
    }
}

关键技巧：在while循环内部处理"下一个更小"，在while循环外部处理"前一个更小"。一次遍历同时完成两种计算。

复杂度分析：时间复杂度$O(n)$，空间复杂度$O(n)$。

字符串问题：字典序优化

单调栈不仅适用于数值数组，还可以用于字符串的字典序优化问题。

LeetCode 402. Remove K Digits

题目描述：给定数字字符串num，移除k个数字，使剩余数字最小。

示例：num = "1432219", k = 3，输出"1219"

解题思路：

要让数字最小，应该让高位数字尽可能小。遍历数字时，如果当前数字比栈顶小，且还可以移除，就弹出栈顶——这相当于用更小的数字替换了高位数字。

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stack = new StringBuilder();
        
        for (char c : num.toCharArray()) {
            // 单调递增栈：弹出比当前大的元素，保证字典序最小
            while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            stack.append(c);
        }
        
        // 如果还有剩余的k，从末尾移除
        while (k > 0 && stack.length() > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }
        
        // 移除前导零
        while (stack.length() > 0 && stack.charAt(0) == '0') {
            stack.deleteCharAt(0);
        }
        
        return stack.length() == 0 ? "0" : stack.toString();
    }
}

LeetCode 316. Remove Duplicate Letters

题目描述：移除字符串中的重复字母，使每个字母只出现一次，且结果字典序最小。

示例：s = "bcabc"，输出"abc"

解题思路：

与移除K位数字类似，但需要额外约束：不能移除"最后一次出现"的字母，否则结果会缺少该字母。

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];  // 剩余出现次数
        boolean[] inStack = new boolean[26];  // 是否已在结果中
        
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        
        StringBuilder stack = new StringBuilder();
        
        for (char c : s.toCharArray()) {
            count[c - 'a']--;
            
            if (inStack[c - 'a']) continue;  // 已在结果中，跳过
            
            // 单调递增栈：弹出比当前大的元素（前提是后面还会出现）
            while (stack.length() > 0 && stack.charAt(stack.length() - 1) > c 
                   && count[stack.charAt(stack.length() - 1) - 'a'] > 0) {
                inStack[stack.charAt(stack.length() - 1) - 'a'] = false;
                stack.deleteCharAt(stack.length() - 1);
            }
            
            stack.append(c);
            inStack[c - 'a'] = true;
        }
        
        return stack.toString();
    }
}

关键点：用count数组记录每个字符剩余的出现次数，只有当"后面还会出现"时才能弹出。

链表上的单调栈

LeetCode 1019. Next Greater Node In Linked List

单调栈同样适用于链表问题，只是需要先将链表转换为数组或列表。

题目描述：对链表每个节点，返回下一个更大节点的值。

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        // 先转换为列表
        List<Integer> values = new ArrayList<>();
        while (head != null) {
            values.add(head.val);
            head = head.next;
        }
        
        int n = values.size();
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && values.get(stack.peek()) < values.get(i)) {
                result[stack.pop()] = values.get(i);
            }
            stack.push(i);
        }
        
        return result;
    }
}

时间复杂度为何是O(n)

初看单调栈代码，很多人会疑惑：明明有嵌套的while循环，为什么时间复杂度是$O(n)$而不是$O(n^2)$？

关键在于每个元素最多被处理两次：一次入栈，一次出栈。虽然while循环看似在"重复"执行，但每个元素在整个算法执行过程中只会被弹出一次。用摊还分析的角度来看：

  • 外层for循环执行$n$次
  • 所有入栈操作总共$n$次
  • 所有出栈操作总共$n$次

总操作次数为$O(3n) = O(n)$。

这与暴力解法的嵌套循环有本质区别：暴力解法中内层循环的指针会不断回退，导致同一元素被重复比较多次。而单调栈通过维护有序性，确保每个元素只参与有限次比较。

LeetCode单调栈题目分类

类型 题目编号 难度
下一个更大元素 496, 503, 556, 1019 Easy/Medium
每日温度 739 Medium
接雨水 42 Hard
柱状图矩形 84, 85 Hard
字符串优化 402, 316, 1081 Medium
海洋视野 1762 Medium
132模式 456 Medium
股票跨度 901 Medium
可见人数 1944 Hard
最大数 321 Hard

刷题顺序建议：

  1. 入门：496 → 739 → 503
  2. 进阶：42 → 84
  3. 字符串：402 → 316
  4. 挑战：456 → 901 → 321

实战技巧与常见陷阱

技巧一：存储索引而非值

栈中存储索引（或指针）而非元素值，这样可以：

  • 通过索引访问原数组的值
  • 计算元素之间的距离
  • 处理重复元素时区分不同位置

技巧二：虚拟边界

对于需要处理"边界外"的问题，可以在数组两端添加虚拟元素：

  • 接雨水问题可以在两端添加高度为0的柱子
  • 柱状图问题可以添加高度为0的哨兵

技巧三：循环数组的处理

循环数组可以通过"虚拟延长"解决，但要注意：

  • 使用取模运算i % n访问元素
  • 第二遍循环时不再入栈，避免重复

陷阱一：严格与非严格的区分

求"下一个更大元素"通常用非严格单调栈（<），而求"前一个更大元素"用严格单调栈（<=）。混用会导致边界错误。

陷阱二：空栈判断

在弹出元素后访问新栈顶时，必须先检查栈是否为空。否则会抛出异常。

陷阱三：前导零处理

在字符串问题中，移除元素后可能出现前导零，需要额外处理。

单调栈作为一种"空间换时间"的优化技巧，其核心价值在于将$O(n^2)$的暴力解法优化到$O(n)$。掌握单调栈的关键是理解"等待"的概念——栈中存储的是等待答案的元素，而栈的单调性保证了我们能高效地为这些等待者找到答案。从下一个更大元素到接雨水，从柱状图到字符串优化，单调栈展现了解决区间边界问题的强大能力。

参考资料

  1. Monotonic Stack - Guide + List of Problems - LeetCode Discuss
  2. A comprehensive guide and template for monotonic stack based problems - LeetCode Discuss
  3. Introduction to Monotonic Stack - AlgoMaster.io
  4. Trapping Rain Water Problem - GeeksforGeeks
  5. Largest Rectangle in Histogram - AlgoMaster.io
  6. Introduction to Monotonic Stack - GeeksforGeeks
  7. Monotonic Stack | Hello Interview