单调栈：O(n) 求下一个更大元素

从 LC 739 每日温度开始：单调栈如何在 O(n) 内解决"对每个 i 找右边第一个 X"这一族问题。

Medium预计阅读 45 分钟更新于 2026-05-17

1. 核心原理

单调栈（monotonic stack）是一种内部元素始终保持单调性（从栈底到栈顶单调递增或单调递减）的栈。它的典型应用场景是这样一个问题模板：

给定一个数组 nums，对每个下标 i，求它右边（或左边）第一个满足条件 P 的下标。

把条件 P 替换成"严格大于 nums[i]"、"大于等于 nums[i]"、"小于 nums[i]"等，都可以用同一份单调栈代码在 O(n) 时间内一次性算出全部答案。本章讨论"右边第一个更大"这一支，母题是 LeetCode 739 每日温度。

暴力解的瓶颈

对每个下标 i 单独向右线性扫直到遇到更大值，时间复杂度 O(n²)，空间 O(1)。在 n ≤ 10⁵ 量级的数据范围下，最坏 10¹⁰ 次比较，无法在 1 秒内完成。瓶颈出在每个 i 的扫描互相独立、不共享中间结果：当某次扫描到下标 j 时，下标 i+1, i+2, …, j-1 之间已经获得的"它们都还在等更大值"这一信息被丢弃，下一轮再次从头计算。

单调栈维护的不变量

引入一个栈，栈中存储下标。不变量：栈中所有下标对应的数组值，从栈底到栈顶严格递减。其含义是——栈中保存的是"目前为止还没有遇到右侧更大值"的所有下标。

从左到右扫描数组。对当前下标 i：

若栈非空且 nums[stack[-1]] < nums[i]，则栈顶下标 j 找到了它的"右边第一个更大值"，即 i。将 j 出栈并记录 ans[j]。
重复第 1 步，直到栈空或栈顶值 ≥ nums[i]。
将 i 入栈。

扫描结束后，栈中剩下的下标在数组右侧没有比它们更大的元素，按题目语义填默认值（如 -1 或 0）。

复杂度

每个下标至多入栈一次、出栈一次，总操作数 ≤ 2n。整体时间 O(n)，空间 O(n)（栈在最坏情况下需存储全部下标，例如严格递减数组 [5, 4, 3, 2, 1]）。

这一摊还（amortized）分析与动态数组扩容、并查集路径压缩属于同一类技巧：内层 while 单次最坏 O(n)，但所有外层迭代的 while 操作总数 O(n)。

五种"两侧第一个 X"的速查表

把 P 替换为不同的比较条件，模板的方向、扫描顺序与 pop 条件按下表配置：

求什么	栈的方向	扫描方向	pop 条件
下一个更大元素（右）	单调递减	从左到右	`nums[stack[-1]] < nums[i]`
下一个更大或等于（右）	单调严格递减	从左到右	`nums[stack[-1]] <= nums[i]`
下一个更小元素（右）	单调递增	从左到右	`nums[stack[-1]] > nums[i]`
上一个更大元素（左）	单调递减	从右到左	`nums[stack[-1]] < nums[i]`
上一个更小元素（左）	单调递增	从右到左	`nums[stack[-1]] > nums[i]`

栈里的元素从栈底到栈顶是等待中的候选答案，方向与被结算时机由 pop 条件决定。

2. 通用模板

下面给出"对每个下标找右侧第一个严格更大值"的通用骨架。代码中栈存储下标（而非值），便于回算距离 i - j 或定位 nums[j]。

def next_greater(nums: list[int]) -> list[int]:
    """
    对每个 i，返回右边第一个 nums[j] > nums[i] 的下标 j。
    若不存在，记 -1。
    """
    n = len(nums)
    ans = [-1] * n
    stack = []                                  # 存下标；对应值从底到顶严格递减
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            j = stack.pop()                     # 栈顶找到了右侧更大值
            ans[j] = i                          # 也可改为 ans[j] = i - j 记距离
        stack.append(i)
    # 扫描结束后，栈中剩余下标右侧没有更大值，ans 保持 -1
    return ans

public int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();   // 存下标
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int j = stack.pop();                 // 栈顶找到了右侧更大值
            ans[j] = i;                          // 也可改为 ans[j] = i - j 记距离
        }
        stack.push(i);
    }
    // 栈中剩余下标右侧没有更大值，ans 保持 -1
    return ans;
}

vector<int> nextGreater(vector<int>& nums) {
    int n = (int) nums.size();
    vector<int> ans(n, -1);
    stack<int> st;                               // 存下标；对应值从底到顶严格递减
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            int j = st.top();                    // 栈顶找到了右侧更大值
            st.pop();
            ans[j] = i;                          // 也可改为 ans[j] = i - j 记距离
        }
        st.push(i);
    }
    // 栈中剩余下标右侧没有更大值，ans 保持 -1
    return ans;
}

模板上有四处可调，决定它能套住哪一族题：

方向（递增 / 递减栈）：找"右侧更大"用单调递减栈（pop 条件 nums[stack.top()] < nums[i]）；找"右侧更小"用单调递增栈（pop 条件 nums[stack.top()] > nums[i]）。
严格性（< vs <=）：< 意味着相等的下标可以并存于栈中（保留较早的位置）；<= 意味着遇到相等就把栈顶挤出。默认用 <，少数题（如直方图合并相等高度）用 <=。
扫描方向（从左到右 / 从右到左）：找"右侧第一个 X"通常从左到右；找"左侧第一个 X"通常从右到左。
栈中存什么（下标 / 值）：存下标信息更丰富（可回算距离、可索引原数组），存值仅在题目完全不需要位置时使用（例如配合哈希表查询）。

3. 母题精讲

LeetCode 739 每日温度

链接：LeetCode 739

题意：给一个整数数组 temperatures，其中 temperatures[i] 表示第 i 天的气温。请返回一个数组 answer，让 answer[i] 表示从第 i 天起还需要再等多少天才能遇到气温更高的一天。如果之后任意一天都不会更暖，answer[i] 取 0。

数据范围：

temperatures.length：1 到 10⁵
temperatures[i]：30 到 100

示例：

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

暴力解：O(n²) 为什么不行？

最直觉的写法就是双层循环——外层枚举 i，内层从 i+1 一直扫到找到更大的那一天，谁都能想出来：

class Solution:
    def dailyTemperatures_brute(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        ans = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    ans[i] = j - i
                    break
        return ans

时间 O(n²)，空间 O(1)。在数据范围 n ≤ 10⁵ 下，最坏 10¹⁰ 次操作，秒级 TLE。

问题出在哪？暴力解里每个 i 都从零开始往右扫，前面 i-1 那次扫到的信息全扔了。这种"对每个 i 找右边第一个满足某条件的元素"的模式在很多题里出现，需要想个法子把前面扫过的信息留下来用。

把被挡住的元素留着排队

把暴力的扫描方式反过来想：从左到右扫到第 i 天时，前面所有 j < i 中"还没等到更暖一天"的位置，本质上都是一群还在等比自己更高温度的下标。temperatures[i] 一来，比它矮的全部"得救"了——i 就是它们等的那一天。

于是有一个想法：维护一个"还在等待中"的下标集合，从左到右扫。每来一个新元素 temperatures[i]，把集合中所有 temperatures[j] < temperatures[i] 的 j 全部结算掉（它们等到的就是 i 这一天）。

这个"集合"该用什么数据结构？你看，最近压进集合的下标，对应的温度肯定 ≤ 比它更早进集合的下标（否则更早的早就被它结算了）。换句话说，集合里的温度从底部到顶部是单调递减的。这就是栈——底部是最早进入、温度最高的；顶部是最近进入、温度最低的。

每来一个新元素，pop 栈顶比它矮的下标（结算它们的答案），再把自己 push 进去。每个元素至多 push 一次、pop 一次——总操作 O(n)。

框架：维护一个还在等更大值出现的栈，新元素来时弹出所有比它矮的并结算。

下面这个交互演示走一遍 [73, 74, 75, 71, 69, 72, 76, 73] 的过程，红色表示"还在栈中等待"的位置，金色是当前轮被结算的位置：

dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])

单调递减栈（存下标），从左到右扫，遇到更高就结算栈顶

Step 1 / 9初始：栈空，answer = [0,0,0,0,0,0,0,0]

index

01234567

value

↑i

还在栈中等待当前轮结算已经结算完毕尚未扫到

01/09

最终 answer = [1, 1, 4, 2, 1, 1, 0, 0]。整个过程每个下标进栈恰好一次、出栈最多一次，总操作 O(n)。

这种"从底到顶单调递减"的栈就叫单调栈——更精确地说是单调递减栈。下面进入例题串讲。

4. 例题串讲

下面三道题按"数组结构递增"排：单数组 → 环形数组 → 两个关联数组。每道带 follow-up 直接续到下一题。

4.1 LC 739 每日温度

链接：LeetCode 739

题意：给一个整数数组 temperatures 表示每天的气温。返回数组 answer，让 answer[i] 表示从第 i 天起再过多少天可以遇到更高的气温；如果之后任意一天都不会更暖，记 0。要求 O(n)。

数据范围：

temperatures.length：1 到 10⁵
temperatures[i]：30 到 100

示例：

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

回到本章开头那道题。直接套上面的模板，把"找下一个更大下标 j"改成"答案存 j − i"（题目要的是天数差，不是下标本身），其他一字不改：

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        ans = [0] * n                                 # 默认 0，找不到就保留
        stack = []
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                ans[j] = i - j
            stack.append(i)
        return ans

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int j = stack.pop();
                ans[j] = i - j;
            }
            stack.push(i);
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n, 0);                          // 默认 0，找不到就保留
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
                int j = st.top(); st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        return ans;
    }
};

复杂度：时间 O(n)、空间 O(n)（栈最坏存全部下标，比如严格递减数组 [5,4,3,2,1]）。

Follow-up：如果数组不是线性的，而是首尾相连的环形数组呢——比如 [1, 2, 1]，最后一个 1 的"下一个更大"应该绕回来看到 2。

4.2 LC 503 下一个更大元素 II

链接：LeetCode 503

题意：给一个循环整数数组 nums（最后一个元素的下一个是第一个元素）。对每个 i，找它在循环意义下下一个更大的元素的值。如果不存在，记 −1。

数据范围：

nums.length：1 到 10⁴
nums[i]：−10⁹ 到 10⁹

示例：

输入：nums = [1, 2, 1]
输出：[2, -1, 2]
解释：i=2 的元素是 1，循环往后看到 nums[0]=1（不够大）、nums[1]=2（够大）→ 答案 2。

环形数组的标准处理套路：把数组在脑子里拼接成自身两倍（nums + nums），扫一遍 2n 长度，但只在前 n 个下标上写答案——后 n 个下标只用来"喂"前 n 个还未结算的位置。代码上不必真的复制数组，用 i % n 即可。

class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [-1] * n
        stack = []
        for i in range(2 * n):                        # 走两遍，模拟拼接
            x = nums[i % n]
            while stack and nums[stack[-1]] < x:
                j = stack.pop()
                ans[j] = x
            if i < n:                                  # 只在第一遍 push 下标
                stack.append(i)
        return ans

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < 2 * n; i++) {
            int x = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < x) {
                int j = stack.pop();
                ans[j] = x;
            }
            if (i < n) stack.push(i);   // 只在第一遍 push
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> st;
        for (int i = 0; i < 2 * n; i++) {               // 走两遍，模拟拼接
            int x = nums[i % n];
            while (!st.empty() && nums[st.top()] < x) {
                ans[st.top()] = x;
                st.pop();
            }
            if (i < n) st.push(i);                       // 只在第一遍 push 下标
        }
        return ans;
    }
};

这里有个坑：第二遍只 pop 不 push。原因是栈里只保留"等待中的真实位置"，第二遍走是为了给第一遍剩在栈里的位置一次额外的机会。如果第二遍也 push，会出现"自己等自己"的死循环。

复杂度仍是 O(n)——每个下标至多 push 一次、pop 一次。一句话：环形 = 拼两遍 + 第二遍只 pop。

Follow-up：上面两题都是"一个数组里自己找自己"。如果题目给了两个数组，其中一个是另一个的子集，要求把第二个数组的单调栈结果"映射"给第一个数组呢？

4.3 LC 496 下一个更大元素 I

链接：LeetCode 496

题意：给两个不重复整数数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对 nums1 中每个元素 x，在 nums2 中找 x 的下一个更大元素并返回。

数据范围：

nums1.length：1 到 1000
nums2.length：1 到 1000
nums1[i]、nums2[i]：0 到 10⁴
nums1 的所有元素都在 nums2 中出现，且各自不重复

示例：

输入：nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
输出：[-1, 3, -1]
解释：
- 4 在 nums2 中没有下一个更大 → -1
- 1 在 nums2 中下一个更大是 3
- 2 在 nums2 中没有下一个更大 → -1

朴素思路：对每个 nums1[i]，在 nums2 里线性扫——O(m × n)。m, n ≤ 1000 下能 AC，但不够优雅。

O(n + m) 套路：先用单调栈在 nums2 上一次性算出"每个元素的下一个更大"，结果存进 hashmap（key = 值，value = 下一个更大元素），然后对 nums1 查表即可。

class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # 第一步：在 nums2 上跑单调栈，得到 next_greater map
        ng = {}                                       # value → next greater value
        stack = []
        for x in nums2:
            while stack and stack[-1] < x:
                ng[stack.pop()] = x
            stack.append(x)
        # 第二步：查表给 nums1 的答案，找不到返回 -1
        return [ng.get(x, -1) for x in nums1]

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> ng = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int x : nums2) {
            while (!stack.isEmpty() && stack.peek() < x) {
                ng.put(stack.pop(), x);
            }
            stack.push(x);
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = ng.getOrDefault(nums1[i], -1);
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // 第一步：在 nums2 上跑单调栈，得到 next_greater map
        unordered_map<int, int> ng;                     // value → next greater value
        stack<int> st;
        for (int x : nums2) {
            while (!st.empty() && st.top() < x) {
                ng[st.top()] = x;
                st.pop();
            }
            st.push(x);
        }
        // 第二步：查表给 nums1 的答案，找不到返回 -1
        vector<int> ans(nums1.size());
        for (int i = 0; i < (int)nums1.size(); i++) {
            auto it = ng.find(nums1[i]);
            ans[i] = it == ng.end() ? -1 : it->second;
        }
        return ans;
    }
};