单调栈（Monotonic Stack）的应用与解析

知识点描述
单调栈是一种特殊的数据结构，它在栈的基础上增加了一个约束：栈内的元素（通常是索引或值）必须按照某种单调性（单调递增或单调递减）排列。单调栈常用于解决一类“在序列中寻找每个元素左侧/右侧第一个比它大/小的元素”的问题，时间复杂度可以优化到O(n)。典型的应用场景包括：柱状图中最大矩形、每日温度、下一个更大元素等。

解题过程详解
我们以经典问题“下一个更大元素”（LeetCode 496. Next Greater Element I）为例，循序渐进讲解单调栈的运作原理。题目简述：给定两个无重复元素的数组nums1和nums2，其中nums1是nums2的子集。对于nums1中的每个元素，找到它在nums2中相同数值元素右侧的第一个更大元素。如果不存在，输出-1。

步骤1：问题转换
核心是为nums2的每个元素找出其右侧第一个更大元素，然后将结果映射到nums1。如果直接对每个元素向右扫描，时间复杂度为O(n²)。单调栈可以帮助我们一次遍历完成。

步骤2：单调栈的选择
由于要寻找“右侧第一个更大元素”，我们维护一个单调递减栈：

• 从栈底到栈顶，元素值递减。
• 当新元素比栈顶大时，栈顶元素就找到了“右侧第一个更大元素”（即新元素）。
• 弹出栈顶，新元素继续与新的栈顶比较，直到栈空或栈顶≥新元素。
• 新元素入栈，保持单调性。

步骤3：模拟执行过程
以nums2 = [3, 2, 4, 1, 5]为例：

1. 栈空，3入栈。栈：[3]（索引0）。
2. 当前元素2，2 < 栈顶3，直接入栈。栈：[3, 2]。
3. 当前元素4，4 > 栈顶2 → 2的右侧第一个更大元素是4。弹出2，记录{2:4}。
   继续比较：4 > 栈顶3 → 3的右侧第一个更大元素是4。弹出3，记录{3:4}。栈空，4入栈。栈：[4]。
4. 当前元素1，1 < 栈顶4，入栈。栈：[4, 1]。
5. 当前元素5，5 > 栈顶1 → 1的右侧第一个更大元素是5。弹出1，记录{1:5}。
   继续比较：5 > 栈顶4 → 4的右侧第一个更大元素是5。弹出4，记录{4:5}。栈空，5入栈。栈：[5]。
6. 遍历结束，栈中剩余元素右侧无更大元素，对应输出-1。

结果映射：{3→4, 2→4, 4→5, 1→5, 5→-1}。对nums1查询此映射即可。

步骤4：代码框架

def nextGreaterElement(nums1, nums2):
    stack = []
    next_greater = {}  # 存储nums2中每个元素的下一个更大元素
    
    for num in nums2:
        while stack and stack[-1] < num:  # 当新元素大于栈顶
            smaller = stack.pop()
            next_greater[smaller] = num
        stack.append(num)
    
    # 栈中剩余元素没有下一个更大元素
    for num in stack:
        next_greater[num] = -1
    
    return [next_greater[num] for num in nums1]

步骤5：复杂度分析

• 时间复杂度：O(n)，每个元素最多入栈和出栈一次。
• 空间复杂度：O(n)，用于栈和哈希表。

步骤6：变体与应用扩展

1. 循环数组：将数组复制一份接在后面，或用取模运算模拟遍历两遍。
2. 左侧第一个更大元素：从右向左遍历，维护单调递减栈。
3. 柱状图最大矩形：对每个高度，用单调栈找到左右第一个比它矮的柱子，从而确定宽度。

核心思想总结
单调栈通过维护一个单调性的栈，在遍历过程中高效地确定每个元素的边界。关键点：

• 根据问题需求选择单调递增或递减栈。
• 通常在出栈时计算答案。
• 适合解决“下一个更大/更小元素”、“视野问题”、“最大面积”等场景。