单调栈和单调队列可以很简单

大家好，我是 方圆。我觉得单调栈和单调队列的题目很有特点，而且理解了它的特点能够很轻松容易地解决一系列题目，所以决定用这篇帖子记录一下，也想以此来帮助在刷同样类型题目的朋友们。如果大家想要找刷题路线的话，可以参考 Github: LeetCode。

1. 单调栈

单调栈本质上是 维护数组中的元素为单调序列，数组中的元素 要么 符合单调性顺利进栈，要么 不符合单调性而将栈中其他元素“挤走”再进栈，使得栈中序列始终满足单调性。

理解这一点很重要，我们以单调递增栈为例，如果出现了比栈顶元素 小 的值，即不符合当前栈中序列单增特性的值，那么它会使所有比它大的值出栈，而 该值便是接下来要连续出栈元素右侧最近的小值，比该值大的栈元素都出栈完毕后，该值进栈，使得栈中的序列仍然满足单调递增。

如果题目有 在连续序列中找元素左/右侧最近的大/小值 的特点，我们就可以使用单调栈来求解，找最近的小值的单调递增栈模板如下，注意入栈的是数组元素的 索引 而不是元素值：

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
        int index = stack.pop();
        
        // 关于 index 的特殊处理
        process();
    }
    // 索引入栈
    stack.push(i);
    
    // 处理逻辑
    process1();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这个模板其实很好记，根据想找小值还是找大值来确定模板中的 while 条件，如果找小值则使用小于号，则 nums[i] < nums[stack.peek()]，如果找大值则使用大于号，则 nums[i] > nums[stack.peek()]，再根据题意判断是否需要给大于小于号添加上等号（这一点考虑是在有重复值出现的情况下）。

说了这么多，其实我们只需要考虑 要找的是最近的小值还是大值，写对应的模板解题即可，即使你没明白为什么单调栈能找元素最近的大/小值（应该自己 Debug 学习一下）也没关系，只要使用了单调栈它就有这个性质，其他的全是虚妄…

相关题目

• 1475. 商品折扣后的最终价格 简单

• 739. 每日温度 中等

• 901. 股票价格跨度 中等

本题其实是逆序遍历数组找左侧最近的大值的题目，能理解这一点就很简单。

• 496. 下一个更大元素 I 简单

如果不用模拟法而是一定要采用单调栈法的话，我觉得这道题甚至比下一道题要难一些。

• 503. 下一个更大元素 II 中等

• 42. 接雨水 困难

接雨水是这些题中比较困难且经典的单调栈应用题，它的要点是找每个柱子两端最近的高柱子，这样才能接到雨水。而找高柱子正对应了要找大值的特点，可以使用单调递减栈模板来解决，正序遍历数组找到能 元素右侧最近的高柱子，而找到高柱子该元素需要出栈，若出栈后栈中还有元素的话，那么该元素为 出栈元素左侧最近的高柱子，所以我们可以得出结论 单调栈能够同时找到元素左右两侧最近的大值/小值。这样，我们就能找到当前柱子左右两边的高柱子，也就可以计算面积了。

1.1 计算当前值作为区间最大值/最小值的最大区间范围

该类型题目不直接要求找某元素左/右侧最近的大/小值，而是利用单调栈能找到某元素最近的大值/小值的特点来 确定当前元素作为区间内最大值/最小值时的区间范围（注意其中的关键字，是作为），以此来计算该元素对题解的"贡献"。

我们初始化每个元素的默认区间范围如下，这是该元素作为极值时的特殊情况：

int[] left = new int[nums.length];
Arrays.fill(left, -1);
int[] right = new int[nums.length];
Arrays.fill(right, nums.length);
1
2
3
4

以当前元素作为区间内最大值为例，记录每个元素能到达的左侧/右侧的最远距离：

Stack<Integer> stack = new Stack<>();

// 正序遍历计算上界
for(int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
        right[stack.pop()] = i;    
    }  
    stack.push(i);
}
stack.clear();
// 逆序遍历计算下界
for (int i = nums.length - 1; i >= 0; i--) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        left[stack.pop()] = i;
    }
    stack.push(i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注意，记录的区间范围为全开区间，所以如果在计算区间长度时需要减 1，而且当题目中没有规定所有值都不同时，需要为其中一个（正序或逆序）遍历条件增加等号，避免发生“重复统计”。

相关题目

• 795. 区间子数组个数 中等

本题是需要找到每个元素作为区间最大值的区间范围，并使用 乘法原理 计算出所有包含该元素的子数组数量

我们以如下例子来解释什么是重复统计：

在不加等号的情况下，如果两个相同的值间不存在比它们还大的值，那么它们在统计自己的区间范围时会越过对方的位置，如上图所示，（无等号情况时）两个 3 的区间范围会相同，那么统计的子数组必然存在重复。如果我们能在正序或逆序遍历添加上等号，那么我们统计的区间范围便成了“半开半闭”的范围，那么它们一侧的区间范围相同，一侧的区间范围不同，这样便不会组合出重复的子数组。

PS：我暂时没想到更好的解释办法，如果大家有更好的理解可以写在评论区

• 907. 子数组的最小值之和 中等

本题需要找到每个元素作为区间内最小值的区间范围，使用 乘法原理 计算出包含该元素的子数组数量 (right - i) * (i - left)，这样就能计算出每个元素对题解的贡献

• 84. 柱状图中最大的矩形 困难

本题和上一题的思路一样，都是将每个元素作为区间最大值时找区间范围，只不过本题计算的是最大面积而已

• 85. 最大矩形 困难

本题需要转换成上一题来进行求解，可以看题解中的解题思路

2. 单调队列

单调队列是在单调栈的基础上实现了对 序列的两端操作，所以我们能够使用单调队列获取到 当前序列中的最值（即操作队首元素），来帮助我们解决 区间最值问题。此外 不要局限 在只使用一个单调队列解题，有的题目需要维护两个单调队列来分别记录区间内的最大值和最小值来求解。

理论上使用单调栈能解决的问题单调队列也能解决，不过在我们不需要获取区间最值时还是使用单调栈来求解。

能获取区间最大值（nums[deque.peekFirst()]）的单调递减队列模板如下：

    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
            int index = deque.pollLast();
            // 关于 index 的特殊处理
            process();
        }
        deque.addLast(i);
        
        // 必要处理逻辑
        process1();
    }
1
2
3
4
5
6
7
8
9
10
11
12

相关题目

• 面试题59 - II. 队列的最大值 中等

• 239. 滑动窗口最大值 困难

• 1438. 绝对差不超过限制的最长连续子数组 中等

本题是单调队列和滑动窗口的经典应用题，需要使用两个单调队列分别来记录区间内的最大值和最小值，通过它们来判断绝对差是否符合题意，而滑动窗口则是想通过窗口的滑动来获取最长的子数组长度，在符合题意的情况下“猛猛地”往右滑动，不符合题意了再考虑将窗口缩小。

• 654. 最大二叉树 中等

• 2100. 适合打劫银行的日子 中等

这道题的题解中效率更好的是前缀和的解法，但是我觉得我不能一下就想出来使用前缀和求解，反而结合滑动窗口并维护两个单调队列更容易理解，大家各取所需吧，我把题解放上来供大家参考：

    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        ArrayDeque<Integer> left = new ArrayDeque<>();
        ArrayDeque<Integer> right = new ArrayDeque<>();

        List<Integer> res = new ArrayList<>();
        int leftBegin = 0, leftEnd = 0;
        int rightBegin = time, rightEnd = time;
        while (rightEnd < security.length) {
            while (!left.isEmpty() && security[leftEnd] > security[left.peekLast()]) {
                left.pollLast();
            }
            left.addLast(leftEnd);
            while (!right.isEmpty() && security[rightEnd] < security[right.peekLast()]) {
                right.pollLast();
            }
            right.addLast(rightEnd);

            if (leftEnd - leftBegin == time) {
                if (left.size() == time + 1 && right.size() == time + 1) {
                    res.add(leftEnd);
                }
                if (leftBegin == left.peekFirst()) {
                    left.pollFirst();
                }
                leftBegin++;
                if (rightBegin == right.peekFirst()) {
                    right.pollFirst();
                }
                rightBegin++;
            }

            leftEnd++;
            rightEnd++;
        }

        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

巨人的肩膀

• 【宫水三叶】一题双解 :「单调栈」&「模拟」