目录
- 一、单调栈
- 1.1 什么是单调栈
- 1.2 应用场景
- 1.3 leetcode 练习题
- 二、单调栈实现方案
- 2.1 求解方法
- 2.2 代码模板
一、单调栈
1.1 什么是单调栈
单调栈（Monotonic Stack）是一种特殊的栈数据结构，主要用于解决一些与单调性相关的问题。
单调栈的特点是栈内元素保持单调性，通常是单调递增或单调递减。
注意：这里定义的顺序是从「栈顶」到「栈底」。有的文章里是反过来的。
本文全文以「栈顶」到「栈底」的顺序为基准来描述单调栈。
1.2 应用场景
单调栈可以在时间复杂度为 O ( n ) O(n) O(n) 的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。
这里指的是，数组里面的每个元素的左边或者右边第一个比他大的值，都可以通过一次遍历得到
所以单调栈一般用于解决以下几种问题：
- 寻找左侧第一个比当前元素大的元素。
- 寻找左侧第一个比当前元素小的元素。
- 寻找右侧第一个比当前元素大的元素。 496. 下一个更大元素 I - 力扣（LeetCode）
- 寻找右侧第一个比当前元素小的元素。
1.3 leetcode 练习题
2866. 美丽塔 II - 力扣（LeetCode）
- 下一个更大元素 I（单调栈模板题）
- 下一个更大元素 II
- 下一个更大元素 IV
- 132 模式
- 每日温度
- 股票价格跨度
- 链表中的下一个更大节点
- 表现良好的最长时间段
- 商品折扣后的最终价格
- 使数组按非递减顺序排列
在熟悉单调栈后，我们可以尝试利用单调栈解决更为复杂的问题：
42. 接雨水 - 力扣（LeetCode）
907. 子数组的最小值之和 - 力扣（LeetCode）
二、单调栈实现方案
2.1 求解方法
解法有点绕口，可以简单记为以下三条规则：
-
无论哪种题型，都建议从左到右遍历元素。
-
查找 「比当前元素大的元素」 就用 单调递增栈，查找 「比当前元素小的元素」 就用 单调递减栈。
-
从 「左侧」 查找就看 「插入栈」 时的栈顶元素，从 「右侧」 查找就看 「弹出栈」 时即将插入的元素。（栈底->栈顶->插入元素的顺序是从左到右的, 我们可以从这点来理解并记忆这条规则）
该规则的详细解释查看 算法数据结构——关于单调栈（Monotone Stack）的详细讲解及应用案例-CSDN博客
2.2 代码模板
代码模板撰写顺序：
- 构造单调栈
- 添加从左侧或者右侧查看的代码
以 496. 下一个更大元素 为基础，在实际编写代码的时候，我们首先构造单调栈：
// 单调递减栈 (只有比栈顶元素大的元素才能直接进栈)
for(int num : nums2){
while(!stack.isEmpty() && num <= stack.peek()){
stack.pop(); // 保证栈中保留的都是比 num 小的值
}
stack.push(num);
}
// 单调递增栈（只有比栈顶元素小的元素才能直接进栈）
for(int num : nums2){
while(!stack.isEmpty() && num >= stack.peek()){
stack.pop();
}
stack.push(num);
}
然后，再添加从左侧或者右侧查看的代码 （ -1 表示没有找到最值）
// 单调递增栈， 左边查看
for(int num : nums2){
while(!stack.isEmpty() && num <= stack.peek()){
stack.pop();
}
map.put(num, stack.isEmpty() ? -1 : stack.peek()); // 左边查看
stack.push(num);
}
// 单调递增栈， 左边查看
for(int num : nums2){
while(!stack.isEmpty() && num <= stack.peek()){
map.put(stack.peek(), num); // 右边查看
stack.pop();
}
map.put(num, -1 ); // 保证没有找到最值的元素能够赋值为 -1
stack.push(num);
}
注意：当左边查看时，入栈时， stack.peek() 是 num 的左边第一个最大值； 右边查看时，出栈时，num 是 stack.peek() 的右边第一个最大值。栈底->栈顶->插入元素的顺序是从左到右的, 我们可以从这点来理解并记忆这条规则，从而理解 栈顶 和 插入元素的对应关系。
