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

题目描述：
给定一个数组 nums，要求返回一个等长数组 result，其中 result[i] 表示在 nums 中第 i 个元素之后第一个比 nums[i] 大的元素值；如果不存在这样的元素，则返回 -1。这是一个典型的“下一个更大元素”（Next Greater Element）问题，其核心挑战是如何在线性时间内高效求解，而单调栈（Monotonic Stack）正是解决这类问题的利器。

解题过程：

1. 问题理解与直观思路

• 对于每个元素 nums[i]，我们需要在索引 i 的右侧找到第一个满足 nums[j] > nums[i] 的元素 nums[j]（j > i）。
• 暴力法：对每个 i，遍历 i+1 到 n-1，时间复杂度为 O(n²)，在数组较大时不可行。
• 优化目标：设计一种方法，在一次遍历中完成所有元素的查找，时间复杂度 O(n)。

2. 单调栈的核心思想

• 单调栈是一种特殊的栈，其中的元素保持单调性（递增或递减）。
• 针对本题，我们可以维护一个单调递减栈（栈内元素从栈底到栈顶递减）。
• 基本思路：
  遍历数组，对于当前元素 nums[i]：
  • 如果栈为空或 nums[i] 小于等于栈顶元素对应的值，则将当前索引 i 入栈。
  • 如果 nums[i] 大于栈顶元素对应的值，则说明 nums[i] 是栈顶元素的下一个更大元素，此时不断弹出栈顶元素并记录结果，直到栈为空或当前元素不再大于栈顶元素对应的值，最后将 i 入栈。
• 这样，每个元素只会入栈和出栈一次，总时间复杂度 O(n)。

3. 分步模拟
以数组 nums = [2, 1, 5, 6, 2, 3] 为例，求解下一个更大元素数组 result（初始化为 [-1, -1, -1, -1, -1, -1]）。

• i=0: nums[0]=2，栈空，索引 0 入栈 → 栈 [0]
• i=1: nums[1]=1，1 <= nums[栈顶=0]=2，索引 1 入栈 → 栈 [0, 1]
• i=2: nums[2]=5，5 > nums[栈顶=1]=1 → 弹出栈顶 1，result[1] = 5；
  5 > nums[栈顶=0]=2 → 弹出栈顶 0，result[0] = 5；栈空，索引 2 入栈 → 栈 [2]
• i=3: nums[3]=6，6 > nums[栈顶=2]=5 → 弹出栈顶 2，result[2] = 6；栈空，索引 3 入栈 → 栈 [3]
• i=4: nums[4]=2，2 <= nums[栈顶=3]=6，索引 4 入栈 → 栈 [3, 4]
• i=5: nums[5]=3，3 > nums[栈顶=4]=2 → 弹出栈顶 4，result[4] = 3；
  3 <= nums[栈顶=3]=6，停止弹出，索引 5 入栈 → 栈 [3, 5]
• 遍历结束，栈中剩余索引 [3, 5] 对应的元素没有下一个更大元素，保持 result 中的 -1。
  最终 result = [5, 5, 6, -1, 3, -1]。

4. 算法实现（伪代码）

function nextGreaterElement(nums):
    n = length(nums)
    result = array of size n filled with -1
    stack = empty stack  // 存储索引
    
    for i from 0 to n-1:
        while stack is not empty and nums[i] > nums[stack.top]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.push(i)
    
    return result

5. 变种与扩展应用
单调栈可以灵活应用于多种变体问题，例如：

• 循环数组：将数组视为环形，即最后一个元素的下一个元素是第一个元素。解决方法是将遍历长度扩展到 2n，取模操作访问元素，但只需处理前 n 个元素的结果。
• 上一个更大元素：改为向左寻找，只需从左到右遍历并维护单调递减栈，在入栈前记录结果。
• 每日温度：类似问题，但要求的是下一个更高温度的天数差（索引差），只需将结果记录为 i - idx 即可。
• 柱状图中最大矩形：单调栈可用于高效求解每个柱子作为高度的最大矩形面积。

6. 复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈一次、出栈一次。
• 空间复杂度：O(n)，最坏情况下栈可能存储所有元素的索引。

7. 关键点总结

• 单调栈的核心是利用栈结构维护一个单调序列，从而在遍历过程中快速找到符合条件的前后元素。
• 适用于需要寻找每个元素在序列中“下一个更大/更小元素”的场景，尤其适合线性时间求解。
• 理解栈中元素的单调性方向（递增或递减）是正确应用的关键，这取决于具体问题的比较条件。

通过掌握单调栈的基本原理和变种，你可以高效解决一系列与顺序和大小关系相关的复杂问题。