除了在树的遍历，DFS等常规场景使用栈(Stack)以外，针对某些特定的问题，还能以栈为主要手段进行非常巧妙的解题，栈中数据（通常是整数）的存储以单调递增或者单调递减的形式，新的元素入栈前通常要把小于它的或者大于它的元素出栈，习惯称之为单调栈。

问题的常规解的时间复杂度通常会达到O(n²)或者O(nlogⁿ)，但使用单调栈可以达到O(n)，思路非常的巧妙。

单调栈的特点

单调栈使用的数据结构就是栈，通常存储整数，可以入栈元素的下标，也可以直接把元素入栈。一般当需要计算元素之间的跨度时，比如像求面积，或者求天数时，这需要用元素的下标来计算，所以这时把元素下标入栈更为方便；其他情况直接入栈元素就可以。

单调栈，有二个重要的特性，一是栈，也要后进先出（FILO），二是单调性，栈中的元素要么是递增的要么是递 减的。具体就单调性而言分为两类：

1. 单调递增栈:元素在栈中从栈底到栈顶是由大到小的，由此，出栈的序列是由小到大的，是递增的
2. 单调递减栈:元素在栈中从栈底到栈顶是由小到大的，由此，出栈的序列是由大到小的，是递减的

为了保持单调性，在入栈的时候，需要把破坏单调性的元素出栈，直到能够保持单调性。

可能不同的文章对单调性定义不同，有些是以栈中的顺序为主，有些是以出栈的序列为主，但只是概念上的不同理解而已，本质上并不无差别。本文将以出栈序列来定义。

单调栈的适用性及其代码流程

单调栈利用后进先出和单调性能够在一个一维数组中选出一个『下一个更大元素』或者『下一个更小元素』的序列，从而实现某些问题的解。

代码流程

它的典型流程，以单调递增栈为例，是：

1. 遍历输入列表（或者数组）
2. 如果栈为空，或者当前元素（以下标形式或者元素）大于栈顶，直接入栈
3. 否则，进行清栈：依据题目中某些约束条件，需要把栈中小于当前元素的元素出栈，然后把当前元素入栈
4. 遍历完后，可能还需要清栈，栈中剩余的肯定 是不直接满足某些约束条件的，通常是对栈中元素直接以某些边界条件去计算结果

另外，在实战中，还可以使用『哨兵』来简化逻辑，通常作为栈底，比如把-1（具体的数值需要依题而定）放在栈底，那么判断栈是否为空时就需要检查 是否忆到了哨兵元素。

适用性

单调栈应用范围不算大，它仅适合解决NEG问题，即Next Greater Element，下一个更大元素。注意，这里也可以更小的元素，也可以是前一个。

以一个简单的例子来说明，比如，有一个数组nums = [2, 1, 2, 4, 3]，返回一个等长数组，每个元素是当前索引在原数组中的『下一个更大』元素，如果没有就存-1。比如输入[2,1,2,4,3]就返回[4,2,4,-1,-1]。

这是典型的NEG问题。暴力解法容易想到，二次遍历就能找到，但会达到O(n²)的复杂度。

单调栈就能派上用场：整体思路就是还没有找到『更大』元素的元素先入栈，约束条件就是『更大的元素』，清栈就是把栈中小于当前元素的元素都弹出，因为它们已找到了『更大』元素，具体的：

1. 从前往后遍历，因为需要修改对应索引的值，所以栈中存索引比较方便
2. 栈为空，或者当前元素[i]小于栈顶，就直接入栈
3. 否则，清栈，把栈中小于当前元素出栈，因为它们忆找到『更大』元素了，就是当前元素[i]
4. 遍历完成后，栈中可能有剩余元素，需要清栈，这些元素都没有找到『更大』元素的，直接存-1即可

明显，这里用的是单调递增栈。只遍历一次，所有元素最多只入栈一次，所以时间复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int[] result = new int[nums.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
    if (stack.isEmpty() || nums[stack.peek()] > nums[i]) {
        stack.push(i);
    } else {
        // 清栈
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
             result[stack.pop()] = nums[i];
        }
    }
}
// 清栈
while (!stack.isEmpty()) {
    result[stack.pop()] = -1;
}

同一套路

NEG是一类问题，用单调栈可解，但问题可能会被包装成各种问题，需要能够脱去外衣和内衣看到问题的本质。

比如，输入的是每日温度，找温度更高的一天，或者以身高为背景的问题，如只能看到比你矮的人的发型，如只能与比你矮的人交朋友等等。

典型题目

单调队列

与单调栈思想一样，也是寻找下一个更大元素NGE，或者下一个更小元素NLE，但具体存储容器不是用栈，而是用队列，因为我们可能会从队首（栈底）取出元素，在实际中会用双端队列(Deque，读作dek)，来当容器。队列中的元素会以单调非递减或者单调非递增顺序存储，队首出队即是最大值或者最小值；队尾入队时则能保证队中的单调性，是解决定额滑动窗口一类问题的利器。

典型题目

参考资料

• Monotonic Stack
• Monotonic Stack & Queue
• [数据结构]——单调栈
• 算法学习笔记(67): 单调栈
• 单调栈
• 单调栈技巧总结
• 单调栈
• 刷题笔记6（浅谈单调栈）
• 单调栈和应用实践
• 单调栈(monotonic stack)揭秘
• 单调栈与单调队列算法详解及LeetCode经典题目（Python）