报名参加金石计划1期挑战——瓜分10万奖池，这是我的第2篇文章，点击查看活动详情

引入

阅读本文，你将会收获：

1. 什么是单调栈
2. 单调栈能解决的问题
3. 单调栈经典题目的解法

什么是单调栈

单调栈，与单调队列对应，只是单调队列对应的出队方式是从队头出列，而单调栈则是从栈头弹出（对应单调队列的位置则是队尾出队）。他们遇到使其不再单调的元素的处理方式实际上是一致的。

我们再来回顾一下单调队列和单调栈的入队/栈时对元素的处理方式：

对于单调递减队列/栈来说：当有一个元素准备入队或者入栈时，与队尾/栈顶的元素进行比较，如果该元素比队尾/栈顶要小，则进行入队、入栈。具体详见下图：

我们就以此规则来保证队列和栈的单调性。所以，单调队列和单调栈他们的入队和入栈规则是一致的，无非就是他们出队和出栈是符合队列和栈的特性，仅此而已。

单调栈解决什么问题？

单调栈一般来说是解决NGE（Next Greater Element）问题，就是对于一系列的元素，找到下一个比他大的元素。

使用单调栈解题

496. 下一个更大元素 I - 力扣（LeetCode）

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1： 输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

首先最容易想到的就是暴力解法。使用二重循环可以简单的解决这个问题，但是既然学习了单调栈我们就使用单调栈来解决这个问题。

首先我们明确的是：

1. nums1中的元素不一定存在于 nums2 数组中。
2. 我们通过将nums2中的元素入栈到单调栈（单调递减）中，当有元素需要被弹出时，我们就可以知道即将入队的元素就是即将被弹出元素的第一个较大的值！
3. 完成第二步时，我们需要在nums1中查询是否存在这个即将被弹出的元素。

有了以上的思想，我们可以写出下列代码：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const top = (s) => s[s.length - 1];

    const hash = {};
    // 简历哈希映射，通过值来查询索引。
    for (let i = 0; i < nums1.length; i++) {
        hash[nums1[i]] = i;
    }
    const stack = [nums2[0]];
    const result = new Array(nums1.length).fill(-1);
    for (let i = 1; i < nums2.length; i++) {
        // 单调栈的应用，如果即将入栈的值比栈顶的数值大，就应该单调栈的规则进行弹出。
        while (stack.length && nums2[i] > top(stack)) {
            if (hash[top(stack)] !== void 0) {
                result[hash[top(stack)]] = nums2[i];
            }
            stack.pop();
        }
        stack.push(nums2[i]);
    }
    return result;
};

42. 接雨水 - 力扣（LeetCode）

这道题可以说是十分的经典了。是单调栈的经典应用题目。当然，除了使用单调栈以外，我们也可以使用双指针的解法来进行解答。双指针的解法此处就略了，主要讲解使用单调栈的解法。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

如果我们使用单调栈，我们需要考虑我们到底是使用单调递增的单调栈还是单调递减的单调栈呢？显然，我们应该使用单调递减的单调栈。

因为当有一个较大的元素即将入栈时，“凹坑”就出现了。

这里有几点需要特别的注意：

1. 如果即将入栈的数值与栈顶的数值相当的话，我们应该如何处理？直接入栈处理么？还是将原来的值弹出，再将新值入栈？（其实都可以）
2. 我们在单调栈中存入的是索引值，而不是高度值，因为我们计算雨水的面积时，是通过“宽×高”的方式进行计算的，我们需要知道左边的柱子和右边柱子之间的距离。但是我们进行比较时，则仍然使用的是高度值进行比较。

function top(arr) {
    return arr[arr.length - 1];
}
var trap = function(height) {
let sum = 0;
const stack = [0];
for (let i = 1; i < height.length; i++) {

    if (height[i] < height[top(stack)] {
        // 即将入栈的元素比栈顶元素小，直接入栈
        stack.push(i);
    } else if (height[i] === height[top(stack)]) {
        // 即将入栈的元素和栈顶元素相等，将原来的元素出栈，再将新元素入栈
        stack.pop();
        stack.push(i);
    } else {
        while (stack.length && height[i] > height[top(stack)]) {
            // 即将入栈的元素比栈顶的元素大，向前不断递归，直到遇到栈顶元素不比新元素小位置
            // “凹坑”就是栈顶的元素，
            // 左边柱子则是栈顶元素下面的第一个元素
            // 右边柱子则是即将入栈的元素
            let mid = top(stack);
            stack.pop();
            if (stack.length) {
                let h = Math.min(height[top(stack)], height[i]) - height[mid];
                const w = i - top(stack) - 1;
                sum += h * w;
            }
        }
        stack.push(i);
    }
}
return sum;
}

上述的代码思路比较清晰，但是代码量看起来还是比较多的。我们可以进行一些简化，其实我们发现如果即将入栈的元素与栈顶的元素相等时，其实进行出栈再入栈的操作其实是多余的。所以，进一步我们可以将代码简化如下：

function top(arr) {
    return arr[arr.length - 1];
}
var trap = function(height) {
let sum = 0;
const stack = [0];
for (let i = 1; i < height.length; i++) {
    while (stack.length && height[i] > height[top(stack)]) {
        // 即将入栈的元素比栈顶的元素大，向前不断递归，直到遇到栈顶元素不比新元素小位置
        // “凹坑”就是栈顶的元素，
        // 左边柱子则是栈顶元素下面的第一个元素
        // 右边柱子则是即将入栈的元素
        let mid = top(stack);
        stack.pop();
        if (stack.length) {
            let h = Math.min(height[top(stack)], height[i]) - height[mid];
            const w = i - top(stack) - 1;
            sum += h * w;
        }
    }
    stack.push(i);
}
return sum;
}

Accept! 搞定！

小结

今天学习的单调栈是一种常用于解决NGE（Next Greater Element）问题的 数据结构，除了经典的接雨水以外，在LeetCode上面还有很多的使用单调栈的题目。希望读者有空可以多加练习。

如果你觉得本文对你有用，别忘了给作者点赞~