算法模板 - 单调栈

1. 单调栈概念

单调栈（Monotonic Stack） 指的是栈内元素在从栈顶到栈底的某个方向上具有单调性（递增或递减）。它常被用来在一次线性扫描中解决「对于每个元素，找到下一个更大（或更小）的元素」这类问题。

• 单调递增栈：从栈底到栈顶，值单调递增；通常用于找“下一个更大元素”等。
• 单调递减栈：从栈底到栈顶，值单调递减；通常用于找“下一个更小元素”等。

2. 适用场景

1. 找下一个更大（或更小）元素：
   • 例如「496. 下一个更大元素I」，「503. 下一个更大元素II」等。
2. 求每个元素左侧/右侧第一个比它大/小的元素：
   • 可用于做区间扩展、找左右边界等。
3. 用于排序：
   • 在某些问题中，也可以把单调栈和其它操作结合做排序，不过更多时候使用堆或树结构效率更高。
4. 范围内判定：
   • 如判断某元素左右两边满足某种大小关系的最远边界等。

3. 下一个更大元素 I

3.1 题目描述

LeetCode 496. 下一个更大元素 I (opens new window)

给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素 x，需要在 nums2 中找到 x 对应位置 右侧 第一个比 x 更大的元素。如果不存在，就返回 -1。

返回一个长度为 nums1.length 的数组 ans，其中 ans[i] 表示对应的「下一个更大元素」。

示例 1

输入：nums1 = [4,1,2], nums2 = [1,3,4,2]
输出：[-1,3,-1]

解释：
- 对于4，在nums2中对应位置是nums2[2] = 4，右侧是[2]，没有大于4的元素，返回-1
- 对于1，nums2中对应位置是nums2[0] = 1，右侧有[3,4,2]，第一个比1大的值是3
- 对于2，nums2中对应位置是nums2[3] = 2，无更大元素，返回-1

示例 2

输入：nums1 = [2,4], nums2 = [1,2,3,4]
输出：[3, -1]

解释：
- 对于2，对应nums2中的位置是nums2[1],右侧[3,4],第一个更大元素是3
- 对于4，对应nums2中的位置是nums2[3],右侧空,返回-1

3.2 解法分析

方法一：暴力法

• 对 nums1 中每个元素 x，先在 nums2 找到 x 的位置 index；
• 然后从 index+1 位置往右遍历，看谁是第一个比 x 大的元素；
• 如果找不到，就返回 -1。
• 时间复杂度较高：O(m*n)，其中 m = nums1.length, n = nums2.length。

3.2.1 暴力代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            // 在nums2中找nums1[i]的位置index
            int index = findIndex(nums2, nums1[i]);
            if (index == -1) {
                // 如果没找到元素，按题意可能返回-1，也看具体情况
                res[i] = -1;
                continue;
            }
            // 从index往右找第一个大于nums1[i]的元素
            int nextGreater = -1;
            for (int j = index + 1; j < nums2.length; j++) {
                if (nums2[j] > nums1[i]) {
                    nextGreater = nums2[j];
                    break;
                }
            }
            res[i] = nextGreater;
        }
        return res;
    }

    private int findIndex(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

复杂度：暴力会导致 O(m*n)。

方法二：单调栈

• 我们先在 nums2 中预处理每个元素右边的第一个更大值，下次查询时就能 O(1) 得到；
• 预处理可以用单调栈思路：
  1. 从右往左遍历 nums2；
  2. 维护一个单调递减栈（从栈顶到栈底，值依次变小）；
  3. 若当前元素 nums2[i] 大于等于栈顶元素，则弹出栈顶；直到栈为空或栈顶元素更大于 nums2[i]；
  4. 弹出后的栈顶就是 nums2[i] 右边第一个更大的值（如果栈空则 -1）。
  5. 将 nums2[i] 入栈。
• 最后用一个哈希表 map 记录「nums2[i] -> 右边第一个更大值」，对于 nums1 的每个元素在 map 中直接查询即可。

3.2.2 单调栈代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // map记录nums2中，每个元素的下一个更大元素
        Map<Integer, Integer> map = new HashMap<>();
        // stack维护的是单调递减序列（存的是 nums2 中的值）
        Deque<Integer> stack = new ArrayDeque<>();

        // 从右往左遍历nums2
        for (int i = nums2.length - 1; i >= 0; i--) {
            int num = nums2[i];

            // 弹出所有小于等于当前num的栈顶元素
            // 保证栈顶元素一定是 num 的下一个更大值
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }

            // 栈顶元素就是当前元素num的下一个更大值，如果为空则-1
            map.put(num, stack.isEmpty() ? -1 : stack.peek());

            // 将当前元素num入栈
            stack.push(num);
        }

        // 对nums1中的每个元素，直接查询map
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

解析：

1. 从右到左遍历 nums2，保证每次栈顶是「右侧」而非左侧元素；
2. 栈中的元素保持单调递减；
3. map 用来记录每个 nums2 元素所对应的「下一个更大元素」。
4. 对 nums1 做查询时，就可以 O(1) 返回结果。

复杂度：

• 构建单调栈 O(n)；
• 查询 nums1 元素 O(m)；
• 整体 O(n + m)。

4. 下一个更大元素 II

4.1 题目描述

LeetCode 503. 下一个更大元素 II (opens new window)

给定一个「循环数组」nums，返回每个元素的「下一个更大元素」。这里循环数组指的是 nums 的结尾会“连接”到 nums 的开始，因此在判断某元素的下一个更大元素时，可能需要回到数组前部分去寻找。如果某元素不存在更大的元素，返回 -1。

示例 1

输入: nums = [1,2,1]
输出: [2, -1, 2]

解释:
- 第一个1的下一个更大元素是2
- 数字2的下一个更大元素不存在(返回-1)
- 第二个1的下一个更大元素需要循环搜索，又是2

示例 2

输入: nums = [1,2,3,4,3]
输出: [2,3,4, -1, 4]

解释:
- 1 -> 2
- 2 -> 3
- 3 -> 4
- 4 -> -1
- 3 -> 4(循环回到数组开头)

4.2 解法思路

• 若仅遍历一次 nums，无法找到「循环」场景下右边的更大元素。例如 [2,3,1]，最后的 1 可能还需要看前面的 2。
• 朴素做法：把 nums “拉直”成两倍长度 [nums, nums] 除去最后一个元素，用单调栈方法处理即可。但会显式地构造一个大小为 2n 的数组。
• 实际可「取模」：在索引遍历时 i % n，模拟循环效果；索引遍历到 2n-1 即可（最后一个元素还用不到）。

4.3 代码实现

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // 默认为-1

        // 单调栈存储的是元素下标
        Deque<Integer> stack = new ArrayDeque<>();

        // 扩展遍历2*n - 1次，使用 i % n 获取在原数组中的下标
        for (int i = 0; i < 2 * n - 1; i++) {
            // 计算真实的索引
            int idx = i % n;
            // 栈顶元素如果比nums[idx]小，则说明nums[idx]就是栈顶元素的下一个更大值
            while (!stack.isEmpty() && nums[stack.peek()] < nums[idx]) {
                // 弹出栈顶，更新它的下一个更大元素
                result[stack.pop()] = nums[idx];
            }
            // 当 i < n 时，才需要往栈里放下标（确保放进去的下标只出现在第一轮）
            if (i < n) {
                stack.push(idx);
            }
        }
        return result;
    }
}

解析：

1. 从头到尾遍历两倍长度（2*n - 1），在索引上使用 i % n 来模拟「环状」。
2. 单调递减栈（栈顶到栈底单调递减），当当前元素 nums[idx] 大于栈顶元素时，弹出栈顶并设置 result[栈顶下标] = nums[idx]。
3. 只有 i < n 时才能 push(i)，以避免无限扩大栈；不然会加入重复的下标，多次处理就没必要。

复杂度：

• 遍历 2n 次，单调栈操作每个下标最多进栈出栈一次，整体 O(n)。

5. 单调栈小结

单调栈在「找下一个更大元素」、「找左右边界」这类问题中极其好用。主要思路是：

1. 单调性：维持一个单调递减或递增的栈，让栈顶总是保留「将来有用」的信息。
2. 遇到更大/更小的元素时：弹出栈顶元素，说明当前元素就是栈顶元素所期待的「下一（更大/更小）元素」。
3. 可对循环数组做取模处理：如果数组是环状，需要两倍循环来模拟，从而在一次线性扫描内搞定。

使用时，需记住以下几点：

1. 存下标还是存值：通常存「下标」，这样可以在出栈时为 result[栈顶下标] 赋值；也方便在循环数组场景里使用 % n。
2. 「更大」或「更小」的判断：根据题目需求若找更大元素，则维护单调递减栈；若找更小元素，则维护单调递增栈。
3. 时间复杂度：一般为 O(n)，因为每个元素（或下标）只能进栈出栈各一次。