单调栈实践（二）：应用

D瓜哥

2020-08-02

在单调栈实践（一）：入门中对单调栈做了一个初步介绍，同时使用一个类似单调栈的题目做了入门的尝试。在本文中，将分析正式单调栈的使用案例。

实践： LeetCode 503. 下一个更大元素 II

单调栈主要就是为了解决选择下一个更大或者更小元素的相关问题。来看一下 LeetCode 503. 下一个更大元素 II。

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

如果熟悉单调栈，这道题的解法就一目了然：将数组从后向前遍历，如果单调栈栈顶元素比当前元素小，就将栈顶元素弹出；重复上述操作，直到栈顶元素大于当前元素，或者栈为空。如果栈不为空，则栈顶元素就是当前元素的后继更大元素。代码如下：

/**
 * LeetCode 503. 下一个更大元素 II
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-05 23:08:39
 */
public int[] nextGreaterElements(int[] nums) {
    if (nums == null || nums.length == 0) {
        return nums;
    }
    int[] result = new int[nums.length];
    Deque<Integer> stack = new LinkedList<>();
    // 只需要将数组“拼接”，遍历两遍数组，就可以解决所有元素后继更大元素的问题
    // 从后向前遍历，再加上单调递增栈，就是时间复杂度为 O(n) 的解决方案
    for (int i = 2 * nums.length - 1; i >= 0; i--) {
        // 取余即可获取当前需要处理的元素
        int index = i % nums.length;
        // 在单调栈不为空的情况下，将栈中小于等于当前元素的值都弹出
        while (!stack.isEmpty() && stack.peek() <= nums[index]) {
            stack.pop();
        }
        // 剩下元素既是比当前元素大的后继元素。为空则是没有更大元素
        // 这里还有一个隐含变量：
        // 由于栈是从后向前添加，则栈顶元素距离当前元素更近。
        // 如果栈不为空，则栈顶元素就是符合条件的元素。
        result[index] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[index]);
    }
    return result;
}

使用单调栈，一个关键点是确定使用的是单调递增栈，还是单调递减栈。

这里给大家留一个思考题：本文提供的答案是从后向前遍历数组。尝试一下从前向后遍历数组的解决方案。

实践： LeetCode 42. 接雨水

下面再来看一下： LeetCode 42. 接雨水。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
图 1. LeetCode 42. 接雨水

这道题的解决方案也是使用单调栈：想要能接雨水，那么必须两边高，中间低，才能形成凹槽。符合条件的数据，不就是“选择下一个更大或者更小元素的问题”吗？正好是单调栈的典型应用场景。思路容易理解，但是代码却需要一些技巧。请看：

/**
 * LeetCode 42. 接雨水
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-07-31 17:27:46
 */
public int trap(int[] height) {
    int result = 0;
    Deque<Integer> stack = new LinkedList<>();
    stack.push(0);
    for (int r = 1; r < height.length; r++) {
        // 单调递减，则将小的元素都出栈
        while (!stack.isEmpty() && height[stack.peek()] < height[r]) {
            // 递减栈，栈顶最小。与下一个元素比，栈顶小；
            // 上面判断条件，栈顶与当前位置元素比，也是栈顶小
            int mid = stack.pop();
            if (!stack.isEmpty()) { (1)
                int l = stack.peek();
                // 高h 取两边最小的一个。
                // l 是现栈顶元素大，mid 是前栈顶元素最小，当前元素比 mid 大，
                // 所以，形成了一个凹槽，可以接水
                int h = Math.min(height[l], height[r]) - height[mid];
                int w = r - l - 1;
                int area = h * w;
                result += area;
            }
        }
        stack.push(r);
    }
    return result;
}