排序算法之：利用单调栈（Monotonic Stack）进行“下一个更大元素”（Next Greater Element）的求解与变种应用
字数 2260 2025-12-22 19:07:24

排序算法之：利用单调栈（Monotonic Stack）进行“下一个更大元素”（Next Greater Element）的求解与变种应用

题目描述

给你一个整数数组 nums，你需要为每个元素找出“下一个更大元素”。
“下一个更大元素”定义为：对于数组中的某个元素 nums[i]，在它右侧找到第一个满足 nums[j] > nums[i] 的元素 nums[j]。如果不存在这样的元素，则结果为 -1。

例如：
输入：nums = [2, 1, 2, 4, 3]
输出：[4, 2, 4, -1, -1]
解释：

  • 元素 2 右侧第一个比它大的是 4。
  • 元素 1 右侧第一个比它大的是 2。
  • 第二个 2 右侧第一个比它大的是 4。
  • 元素 4 右侧没有比它大的元素，输出 -1。
  • 元素 3 右侧没有比它大的元素，输出 -1。

解题过程循序渐进讲解

这个问题通常被看作一种“类排序”或“基于顺序的查找”问题，但它的高效解法并不依赖传统的比较排序，而是利用了一种叫做单调栈的数据结构。下面我们一步步来理解。

第一步：理解“下一个更大元素”的直观思路

最直接的想法是对每个元素，向右扫描直到找到比它大的元素。
对于数组长度为 n，最坏情况下需要对每个元素扫描整个右侧部分，时间复杂度是 O(n²)。
当 n 很大时（例如 10⁵），这种方法就太慢了。

我们需要找到一种方法，在扫描数组的过程中，能“记住”还未找到答案的元素，并在遇到更大的元素时，一次性解决多个元素的答案。
这正是单调栈的核心思想。

第二步：引入单调栈的概念

单调栈是一种特殊的栈，它保持栈内元素的某种单调性（单调递增或单调递减）。
在这个问题中，我们想要找到“下一个更大元素”，所以更适合使用单调递减栈（栈内元素从栈底到栈顶是递减的）。

为什么？
因为当我们从左到右遍历数组时：

  • 如果当前元素 ≤ 栈顶元素，说明它不能作为栈内任何元素的“下一个更大元素”，我们把它压入栈，等待后面更大的元素。
  • 如果当前元素 > 栈顶元素，那么它就是栈顶元素的“下一个更大元素”！我们可以弹出栈顶元素，并记录答案。而且，它可能还是栈中更多元素的答案（因为栈是递减的，栈内元素都比当前栈顶小，所以如果当前元素比栈顶大，它可能也比更早入栈的元素大）。

这个过程保证了每个元素只入栈、出栈一次，时间复杂度 O(n)。

第三步：用例子模拟单调栈的工作流程

以 nums = [2, 1, 2, 4, 3] 为例，初始化栈空，结果数组 res = [-1, -1, -1, -1, -1]。

  1. i=0, nums[0]=2
    栈空，入栈（存储索引 0）。栈：[0]（对应值 2）。

  2. i=1, nums[1]=1
    栈顶元素值 2，1 ≤ 2，不满足“当前元素 > 栈顶”，所以入栈（索引 1）。栈：[0, 1]（值 2, 1，递减）。

  3. i=2, nums[2]=2
    栈顶元素值 1，2 > 1，触发弹出：

    • 弹出栈顶索引 1，res[1] = nums[2] = 2。
      此时栈顶为索引 0，对应值 2，2 ≤ 2，不满足大于，所以停止弹出。
      将当前索引 2 入栈。栈：[0, 2]（值 2, 2）。

  4. i=3, nums[3]=4
    栈顶元素值 2，4 > 2，触发弹出：

    • 弹出索引 2，res[2] = 4。
      栈顶变为索引 0，值 2，4 > 2，继续弹出：
    • 弹出索引 0，res[0] = 4。
      栈空，停止弹出。
      入栈当前索引 3。栈：[3]（值 4）。

  5. i=4, nums[4]=3
    栈顶元素值 4，3 ≤ 4，不触发弹出，入栈索引 4。栈：[3, 4]（值 4, 3）。

遍历结束，栈中剩余的元素（索引 3 和 4）右侧没有更大的元素，保持 res 中初始值 -1。
最终结果：res = [4, 2, 4, -1, -1]。

第四步：算法步骤总结

  1. 初始化一个空栈（存储元素索引），初始化结果数组 res 全部为 -1。
  2. 从左到右遍历数组，对于每个索引 i 和值 nums[i]：
    • 当栈不为空，且 nums[i] > nums[栈顶索引] 时：
      • 弹出栈顶索引 top_idx，并令 res[top_idx] = nums[i]。
    • 将当前索引 i 压入栈中。
  3. 遍历结束后，栈中剩下的索引在 res 中仍是 -1（表示没有下一个更大元素）。

第五步：变种应用示例

这个单调栈的模板可以解决一系列“下一个更大/更小元素”的问题，只需调整单调性和比较方向：

  • 下一个更大元素（循环数组）：将数组拉直为两倍长度，用取模运算模拟循环，栈中存储索引仍用原数组长度。
  • 下一个更小元素：改为维护单调递增栈（栈内递增），比较时判断 nums[i] < nums[栈顶]。
  • 上一个更大元素：从右向左遍历，维护单调递减栈。
  • 每日温度：求下一个更高温度的天数间隔，栈中存储索引，结果存 i - top_idx 而不是值。

第六步：关键点与复杂度

  • 核心思想：利用单调栈的单调性，保证每个元素出栈时，当前遍历到的元素就是它的“下一个更大元素”。
  • 时间复杂度：O(n)，每个元素最多入栈、出栈各一次。
  • 空间复杂度：O(n)，最坏情况下所有元素都压入栈。

这个技巧将看似需要 O(n²) 的搜索问题优化到了 O(n)，是处理这类“顺序依赖查找”问题的强大工具。

排序算法之：利用单调栈（Monotonic Stack）进行“下一个更大元素”（Next Greater Element）的求解与变种应用 题目描述 给你一个整数数组 nums ，你需要为每个元素找出“下一个更大元素”。 “下一个更大元素”定义为：对于数组中的某个元素 nums[i] ，在它 右侧 找到第一个满足 nums[j] > nums[i] 的元素 nums[j] 。如果不存在这样的元素，则结果为 -1 。 例如： 输入： nums = [2, 1, 2, 4, 3] 输出： [4, 2, 4, -1, -1] 解释： 元素 2 右侧第一个比它大的是 4。 元素 1 右侧第一个比它大的是 2。 第二个 2 右侧第一个比它大的是 4。 元素 4 右侧没有比它大的元素，输出 -1。 元素 3 右侧没有比它大的元素，输出 -1。 解题过程循序渐进讲解 这个问题通常被看作一种“类排序”或“基于顺序的查找”问题，但它的高效解法并不依赖传统的比较排序，而是利用了一种叫做 单调栈 的数据结构。下面我们一步步来理解。 第一步：理解“下一个更大元素”的直观思路 最直接的想法是对每个元素，向右扫描直到找到比它大的元素。 对于数组长度为 n，最坏情况下需要对每个元素扫描整个右侧部分，时间复杂度是 O(n²)。 当 n 很大时（例如 10⁵），这种方法就太慢了。 我们需要找到一种方法，在扫描数组的过程中，能“记住”还未找到答案的元素，并在遇到更大的元素时，一次性解决多个元素的答案。 这正是单调栈的核心思想。 第二步：引入单调栈的概念 单调栈是一种特殊的栈，它保持栈内元素的某种单调性（单调递增或单调递减）。 在这个问题中，我们想要找到“下一个更大元素”，所以更适合使用 单调递减栈 （栈内元素从栈底到栈顶是递减的）。 为什么？ 因为当我们从左到右遍历数组时： 如果当前元素 ≤ 栈顶元素，说明它不能作为栈内任何元素的“下一个更大元素”，我们把它压入栈，等待后面更大的元素。 如果当前元素 > 栈顶元素，那么它 就是 栈顶元素的“下一个更大元素”！我们可以弹出栈顶元素，并记录答案。而且，它可能还是栈中更多元素的答案（因为栈是递减的，栈内元素都比当前栈顶小，所以如果当前元素比栈顶大，它可能也比更早入栈的元素大）。 这个过程保证了每个元素只入栈、出栈一次，时间复杂度 O(n)。 第三步：用例子模拟单调栈的工作流程 以 nums = [2, 1, 2, 4, 3] 为例，初始化栈空，结果数组 res = [-1, -1, -1, -1, -1] 。 i=0, nums[ 0]=2 栈空，入栈（存储索引 0）。栈：[ 0 ]（对应值 2）。 i=1, nums[ 1]=1 栈顶元素值 2，1 ≤ 2，不满足“当前元素 > 栈顶”，所以入栈（索引 1）。栈：[ 0, 1 ]（值 2, 1，递减）。 i=2, nums[ 2]=2 栈顶元素值 1，2 > 1， 触发弹出 ： 弹出栈顶索引 1， res[1] = nums[2] = 2 。 此时栈顶为索引 0，对应值 2，2 ≤ 2，不满足大于，所以停止弹出。 将当前索引 2 入栈。栈：[ 0, 2 ]（值 2, 2）。 i=3, nums[ 3]=4 栈顶元素值 2，4 > 2，触发弹出： 弹出索引 2， res[2] = 4 。 栈顶变为索引 0，值 2，4 > 2，继续弹出： 弹出索引 0， res[0] = 4 。 栈空，停止弹出。 入栈当前索引 3。栈：[ 3 ]（值 4）。 i=4, nums[ 4]=3 栈顶元素值 4，3 ≤ 4，不触发弹出，入栈索引 4。栈：[ 3, 4 ]（值 4, 3）。 遍历结束，栈中剩余的元素（索引 3 和 4）右侧没有更大的元素，保持 res 中初始值 -1。 最终结果： res = [4, 2, 4, -1, -1] 。 第四步：算法步骤总结 初始化一个空栈（存储元素索引），初始化结果数组 res 全部为 -1。 从左到右遍历数组，对于每个索引 i 和值 nums[i] ： 当栈不为空，且 nums[i] > nums[栈顶索引] 时： 弹出栈顶索引 top_idx ，并令 res[top_idx] = nums[i] 。 将当前索引 i 压入栈中。 遍历结束后，栈中剩下的索引在 res 中仍是 -1（表示没有下一个更大元素）。 第五步：变种应用示例 这个单调栈的模板可以解决一系列“下一个更大/更小元素”的问题，只需调整单调性和比较方向： 下一个更大元素（循环数组） ：将数组拉直为两倍长度，用取模运算模拟循环，栈中存储索引仍用原数组长度。 下一个更小元素 ：改为维护单调递增栈（栈内递增），比较时判断 nums[i] < nums[栈顶] 。 上一个更大元素 ：从右向左遍历，维护单调递减栈。 每日温度 ：求下一个更高温度的天数间隔，栈中存储索引，结果存 i - top_idx 而不是值。 第六步：关键点与复杂度 核心思想：利用单调栈的单调性，保证每个元素出栈时，当前遍历到的元素就是它的“下一个更大元素”。 时间复杂度：O(n)，每个元素最多入栈、出栈各一次。 空间复杂度：O(n)，最坏情况下所有元素都压入栈。 这个技巧将看似需要 O(n²) 的搜索问题优化到了 O(n)，是处理这类“顺序依赖查找”问题的强大工具。