单调栈主要用于解决找到后面比前面大的元素的位置,具体的增加规则就是一旦遇到比栈顶元素大或者小的元素就不断弹出栈顶元素知道栈顶元素不大于或者小于当前元素之后把当前元素入栈即可,不同于单调队列
- 每日温度 经典的单调栈的题目,注意每一次弹出的时候都需要初始化结果数组中的元素值 每日温度.cpp
- 下一个最大元素I 这一个题目需要以
nums2为主体,为nums1的元素和索引之间建立哈希表,之后在对于nums2的单调栈中根据哈希表初始化结果数组即可 下一个最大元素I.cpp - 下一个最大元素II 把数组遍历两边即可(或者利用
vector.insert()方法把数组进行拼接也可以),遍历两边的同时需要建立单调栈,在单调栈中注意把当前元素的下标对于数组长度进行取模运算,其他的都是一样的,对于当前元素等于栈顶元素的情况为了两个都可以得到更新可以入栈 下一个最大元素II.cpp - 接雨水 字节的经典面试题,注意此时需要考虑三个元素： 当前元素,栈顶元素和栈顶元素的下一个元素,其实这一个过程可以是连续的,也就是只要遇到当前元素大于栈顶元素就就可以开始计算可以扎装的水了,也就是中间的元素已经计算完毕了,只需要计算前面的元素即可,同时也可以使用双指针法,此时只用关注当前元素最多可以装的水量即可: 接雨水.cpp
- 柱状图中的最大矩形 注意这一个题目和接雨水一样都是考虑中间的元素,接雨水中考虑中间的元素可以接多少雨水,可以考虑两边距离这一个元素第一个大于这一个元素的元素位置,所以在这一个区间中就可以接雨水了,但是这一个题目中如果考虑当前元素那么就表示当前元素最长可以延伸到那里,所以需要找到两端小于这一个元素的元素即可,对于双指针法,接雨水时累加所以不用考虑下标这里是延伸所以需要记录下标,总之关注当前位置即可,看当前位置可以延伸到那里: 柱状图中的最大矩形.cpp
- 单调栈总结:
- 单调栈的作用: 找到当前元素右边和左边第一个小于或者大于这一个元素的元素,注意当前元素就是指的栈顶元素
- 单调栈的实现方式: 利用一个栈,加入元素的同时删除小于或者大于这一个元素的元素即可
- 单调栈的使用方式:
- 搞清楚什么是当前元素也就是栈顶元素,一般利用单调栈可以求解左边和右边第一个小于或者大于当前元素的元素,所以一般用于题目中需要考虑三个元素(需要加入的元素,栈顶元素和栈顶元素的下面一个元素)
- 接雨水中关注接下了多少雨水,所以需要找到左边和右边第一个大于当前元素的元素
- 柱状图中的最大矩阵中关注当前元素最大可以延伸到那里,所以需要寻找左边和右边第一个小于当前元素的元素