前言
单调栈是一种比较简单的数据结构。虽然简单，但在某些题目中能发挥很好的作用。
最近很多大厂的笔试、面试中都出现了单调栈的题目，而还有不少小伙伴连单调栈是什么都不了解，因此老汪专门写了这篇文章，希望对你们有所帮助。
老规矩，先上一道题给大家看看单调栈能解决什么样的问题，这题是 2020 年猿辅导（K12 教育的独角兽，研发岗白菜价 40W 起步，不加班高福利，想要内推的可以私信老汪）的一道面试题。
单调栈
翻译成大白话，凡是遇到题目中直接或间接要求查找某个元素左/右边第一个大于/小于它的元素，或者要求将某个元素左/右边所有小/大于它的元素按升/降序输出，就可以使用单调栈来解决。
具体怎么做你可能还有些迷糊，下面我们直接通过做题来加深对单调栈的理解。十分钟包教包会，当天就可以和面试官对线。
初入茅庐
最暴力的解法，就是对每一个 a[i]，遍历其左边的所有元素，这样所需的时间复杂度是 O(n^2)。如果使用单调栈，时间复杂度可以优化到 O(n)。
这是最基本、最直白的单调栈问题，所有单调栈问题都是在该问题上进行延伸、变种得来的，掌握了这个问题的解决方法，所有单调栈的问题都能迎刃而解。
由于本问题过于简单、直白，就不多做讲解，直接上代码：
public int[] solve(int[] a){
if(a == null) return null; //容错处理，越是简单的题越要注意细节
int n = a.length;
int[] b = new int[n];
Stack<Integer> stack = new Stack(); //单调栈当然要用栈结构啦
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && stack.peek() < a[i]) stack.pop(); //所有比 a[i] 小的元素都出栈，保证了从栈顶到栈底元素是单调增的，并且栈顶的元素是 a[i] 左边第一个比 a[i] 大的元素
if(stack.isEmpty()) stack.push(a[i]);
b[i] = stack.peek();
}
return b;
}
这代码也是单调栈问题的基本结构，所有单调栈问题的代码都基于此进行变种、扩展。小伙伴们可以多花两分钟好好消化上面的代码。
考虑到有些小伙伴不用 Java，老汪把上述代码抽象成伪代码，这也是单调栈的基本结构。
背诵 + 套用，即可解决所有单调栈问题。
函数 solve (数组 a):
新建数组 b;
新建栈 stack;
For i From 0 To n - 1:
While 栈非空 且 栈顶元素 < a[i]：
出栈;
End While
If 栈空 Then:
a[i] 入栈;
End If
b[i] = 栈顶元素;
End For
return b;
小试牛刀
单调栈的最基本使用方式我们已经了解了，下面一起来解决文章开头提到的面试题。
最暴力的方法就是对前序序列进行排序，时间复杂度为 O(nlogn)，使用单调栈可以优化到 O(n)。
思路分析：
对于二叉搜索树而言，给定其根节点 a[i]，左子树里所有元素都比 a[i] 小，右子树里所有元素都比 a[i] 大。
回顾一下遍历顺序：
前序序列，先遍历根节点，再遍历左子树，最后遍历右子树；
中序序列，先遍历左子树，再遍历根节点，最后遍历右子树。
即，对于元素 a[i]，以它为根节点的子树，
前序序列为，a[i], a[i] 的左子树序列, a[i] 的右子树序列
后序序列为，a[i] 的左子树序列, a[i]，a[i] 的右子树序列
因此，当我们遍历前序序列，遇到右子树的第一个元素 a[j] 时，其左边所有元素都小于 a[j]， 将其左边所有元素按升序输出，即可得到 a[i] 和 a[i] 的左子树 的后序序列。
对于右子树再以上述步骤迭代，即可得到完整的后序序列。
显然，这是单调栈的第二种用法：单调栈可以将某个元素左边所有比它小的元素按升序输出。
下面直接上代码：
public int[] solve(int[] pre){
if(pre == null) return null; //注意容错细节
int n = pre.length;
int[] infix = new int[n]; //中序序列
Stack<Integer> stack = new Stack();
int index = 0; // 指示中序序列的当前下标
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && stack.peek() < pre[i]) infix[index++] = stack.pop(); //由于栈中元素是从栈顶到栈底单调增的，所以可以保证输出序列是单调增的
stack.push(pre[i]);
}
while(!stack.isEmpty()) infix[index++] = stack.pop();
return infix;
}
打怪升级
再来看一道题，这道题是 2020 年 9 月 6 日字节笔试的第二题。难度对标 leetcode 的 medium 级别。
思路分析：一看题目，就是单调栈的第一种用法。使用两次单调栈分别得到 L[i] 和 R[i]，再遍历一遍即可。时间复杂度为 O(n)。
代码如下：
public int solve(int[] a){
if(a == null) throw new RuntimeException("输入有误！"); //细节，一定要细
int n = a.length;
int[] L = new int[n], R = new int[n];
// 这里分两次 for 循环来写，熟练的话可以放在同一个 for 循环里。
Stack<Pair> stack = new Stack();
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && stack.peek().val < a[i]) stack.pop();
L[i] = stack.isEmpty() ? 0 : stack.peek().id + 1; //注意题目要求下标是从 1 开始的
stack.push(new Pair(i, a[i]));
}
stack.clear();
for(int i = n - 1; i >= 0; i--){
while(!stack.isEmpty() && stack.peek().val < a[i]) stack.pop();
R[i] = stack.isEmpty() ? 0 : stack.peek().id + 1; //注意题目要求下标是从 1 开始的
stack.push(new Pair(i, a[i]));
}
// L[i] 和 R[i] 计算完毕，下面遍历一遍得到最大值即可
int ans = 0;
for(int i = 0; i < n; i++) ans = Math.max(ans, L[i] * R[i]);
return ans;
}
class Pair{
int id; // 下标
int val;
public Pair(int id, int val){
this.id = id;
this.val = val;
}
}
出师试炼
关卡 1
关卡 2
关卡 3
PS：在公众号【往西汪】后台回复关键字【单调栈】，即可获得上述关卡的过关秘籍（代码实现）。
本期单调栈问题就分享到这，下一期你想看什么内容呢？单调队列？前缀和思想？还是老汪独家刷题秘籍？又或者有其他想看的，也可以在下方评论区告诉老汪。
我是往西汪，致力于面向 offer 分享算法知识，希望你早日收获心仪 offer。我们下期再见。