09. 单调递增栈

正文

单调栈（Monotonic Stack）是一种极其重要的数据结构，专门用于解决“下一个更大元素（Next Greater Element）”或“上一个更小元素”这类问题。

算法模板 (寻找下一个更大元素)

fun nextGreaterElement(nums: IntArray): IntArray {
    val n = nums.size
    val result = IntArray(n) { -1 }
    // 栈中存储元素的索引（以便更新 result 数组）
    val stack = mutableListOf<Int>()

    for (i in nums.indices) {
        // 当栈不为空，且当前元素大于栈顶元素时
        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
            // 此时 nums[i] 就是栈顶元素的“下一个更大元素”
            val index = stack.removeAt(stack.size - 1)
            result[index] = nums[i]
        }
        
        // 当前元素入栈（等待属于它的更大元素出现）
        stack.add(i)
    }

    return result
}

使用说明

1. 核心特性：

   • 单调递增栈：栈内元素从底到顶单调递增。用于寻找右侧第一个比自己小的元素（或者左侧第一个比自己小的）。
   • 单调递减栈：栈内元素从底到顶单调递减。用于寻找右侧第一个比自己大的元素（即模板写法）。

2. 核心优势：

   • 将 $O(N^2)$ 的暴力查找优化到 $O(N)$。每个元素最多进栈一次、出栈一次。

3. 常见变形：

   • 循环数组：通过遍历两次（i % n）来模拟循环。
   • 接雨水：利用单调栈计算低洼处的面积。
   • 最大矩形面积：利用单调栈寻找左右两侧的边界。

4. 注意点：

   • 明确题目要求的是“右侧第一个更大”还是“左侧第一个更小”。
   • 明确栈里存的是“元素值”还是“元素的下标”（下标通常更通用）。