单调栈及其应用
单调栈是一种特殊类型的栈，可以用来解决一些特定问题，本文整理了构建单调栈的方式，以及单调栈的一些应用。
<!--more-->
参考：
1. 概念
1.1. 定义
单调栈 是在栈的先进后出基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增或递减。
为了维护栈的单调性，在进栈过程中需要进行判断，具体进栈过程如下：假设当前进栈元素为 e，
- 对于单调递增栈，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直至遇见一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中，这样就能满足从栈顶到栈底的元素是递增的
- 对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素，直至遇见一个小于e的元素或者栈为空为止
单调栈的作用在于
单调递增栈从栈顶到栈底是递增的，栈中保留的都是比当前入栈元素大的值，因此可以快速找到入栈元素左边比他大的元素
单调递减栈从栈顶到栈底是递减的，栈中保留的都是比当前入栈元素小的值，因此可以快速找到入栈元素左边比他小的元素
以[1,3,2,5,4]为例，展示单调递增栈的入栈过程
| 操作 | 结果 | 作用 |
|---|---|---|
| 栈为空，1入栈 | [1] | 左侧无比1大的元素 |
| 3>1，1出栈，栈为空，3入栈 | [3] | 左侧无比3大的元素 |
| 2<3，2入栈，可以确定左侧比2 | [3,2] | 左侧比2大的元素有：3 |
| 5>2，2出栈；5>3，3出栈，栈为空，5入栈 | [5] | 左侧无比5大的元素 |
| 4<5，4入栈 | [5,4] | 左侧比4大的元素有：5 |
同样以[1,3,2,5,4]为例，展示单调递减栈的入栈过程
| 操作 | 结果 | 作用 |
|---|---|---|
| 栈为空，1入栈 | [1] | 左侧无比1小的元素 |
| 3>1，3入栈 | [1,3] | 左侧比3小的元素有：1 |
| 2<3，3出栈；2>1，2入栈 | [1,2] | 左侧比2小的元素有：1 |
| 5>2，5入栈 | [1,2,5] | 左侧比5小的元素有：2,1 |
| 4<5，5出栈；4>2，4入栈 | [1,2,4] | 左侧比4小的元素有：2,1 |
1.2. 递增递减傻傻分不清
在学习时查阅相关资料，有的定义是从从栈顶到栈底单调，有的定义是从从栈底到栈顶单调。
后来发现无需拘泥于这些细节，只要理解了相关的概念和应用即可，因此本文全部使用从栈顶到栈底单调的概念来描述递增栈和递减栈的顺序。
2. 相关例子
单调栈主要解决下面几种问题
- 比当前元素更大的下一个元素
- 比当前元素更大的前一个元素
- 比当前元素更小的下一个元素
- 比当前元素更小的前一个元素
2.1. 每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
根据题意，将列表反转之后，我们所求的就是从当前元素e开始左侧第一个比e的元素，因此可以使用递增栈处理
var dailyTemperatures = function (T) {
T.reverse()
var stack = []
var ans = []
for(var i = 0; i < T.length; ++i){
// 维护递增栈，注意此处栈内保存的是索引值而不是具体的温度
while(stack.length && T[stack[stack.length - 1]] <= T[i]){
stack.pop()
}
if(stack.length){
// 左侧栈中的元素都比当前元素值大，最近一天则取栈顶元素即可
ans[i] = i - stack[stack.length - 1]
}else {
ans[i] = 0
}
stack.push(i)
}
return ans.reverse()
};上面的代码进行了两次翻转，我们可以将其简化
var dailyTemperatures = function (T) {
var ans = new Array(T.length).fill(0)
var stack = []
for(var i = 0; i < T.length; ++i){
// 当碰到一个大于栈顶的元素时，则该元素一定是离栈顶元素最近一天的较高值
while(stack.length && T[stack[stack.length - 1]] < T[i]){
var cur = stack.pop()
ans[cur] = i - cur
}
stack.push(i)
}
return ans
}2.2. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
使用一个栈statck来维护已遍历的元素，如果当前元素大于等于栈底元素的话，就表示形成了一个水槽，此时计算并更新sum，然后重置stack。可以看见这个栈的特殊性：栈内元素都比栈底元素小，即栈底元素为最大值
var trap = function(height) {
var stack = []
var sum = 0
for(var i = 0; i < height.length; ++i){
var cur = height[i]
if(!stack.length || stack[0] > cur){
stack.push(cur)
}else{
var max = stack[0]
for(var j = 0; j < stack.length; ++j){
sum += max - stack[j]
}
stack = [cur]
}
}
// 处理剩余的stack， 由于栈底元素为最大值，因此这里将其翻转后，再进行计算
if(stack.length > 1){
sum += trap(stack.reverse())
}
return sum
};使用用例[0,1,0,2,1,0,1,3,2,1,2,1]，则整个计算过程为
1,0,2，此时sum为12,1,0,1,3，此时sum为1 + 43,2,1,2,1，最后翻转计算，2,1,2，此时sum为1+ 4 + 1- 输出结果6
2.3. 下一个更大的元素
思路：从后向前构建一个递增栈，并保存每一个元素的右侧最大值
var nextGreaterElement = function(nums1, nums2) {
var stack = []
var map = {}
for(var i = nums2.length - 1; i >= 0; --i){
var cur = nums2[i]
while(stack.length && top(stack) < cur){
stack.pop()
}
map[cur] = stack.length ? top(stack) : -1
stack.push(cur)
}
return nums1.map(item=>map[item])
function top(arr){
return arr[arr.length - 1]
}
};这个题的思路与上面类似，只是增加了循环数组的判断，因此可以先判断正向，然后再拼接判断一次
2.4. 最长宽度坡
给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。
本题主要的思路是：正向构造一个递增栈，栈中保存的都是可以作为“坡底”元素的索引值，然后反向从末尾与栈顶元素对应的值进行比较，同时弹出栈顶元素，取较大值作为返回结果
var maxWidthRamp = function (A) {
var stack = []
// 构建递增栈，栈中元素
for(var i = 0; i < A.length; ++i){
if(!stack.length || A[stack[stack.length - 1]] > A[i]){
stack.push(i)
}
}
var ans = 0
for(var i = A.length - 1; i >=0; --i){
while(stack.length && A[stack[stack.length - 1]] <= A[i]){
ans = Math.max(i - stack.pop(), ans)
}
}
return ans
};2.5. 表现良好的最长时间段
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
输入：hours = [9,9,6,0,6,6,9] 输出：3 解释：最长的表现良好时间段是 [9,9,6]。
本题主要思路为
- 将hours转换成score数组，表现良好为1，不良为-1，则题目转换为：score中和大于0的连续子数组的最大长度
- 使用前缀和，前缀和数组中,
presum[j] - presum[i]表示i,j区间的元素和，因此题目转换为：presum 中两个索引 i 和 j，使j - i最大，且保证presum[j] - presum[i] > 0 - 此时与上面的最长坡问题类似，通过单调栈求解最大长度
var longestWPI = function(hours) {
// 题目转换为：求score中和大于0的连续子数组的最大长度
var score = hours.map(item=>{
return item > 8 ? 1 : -1
})
// 使用前缀和
var presum = [0]
score.forEach((item, index)=>{
presum.push(presum[index] + item)
})
// 题目转换为求：presum 中两个索引 i 和 j，使 j - i 最大，且保证 presum[j] - presum[i] > 0，
var stack = []
for(var i = 0; i < presum.length; ++i){
if(!stack.length || presum[stack[stack.length - 1]] > presum[i]){
stack.push(i)
}
}
var ans = 0
for(var i = presum.length-1; i >=0; --i){
while(stack.length && presum[stack[stack.length - 1]] < presum[i]){
ans = Math.max(ans, i - stack.pop())
}
}
return ans
};2.6. 股票价格跨度
思路为：保存一个递增栈，当插入新元素时，与栈顶元素做比较并依次弹出，找到第一个大于当前元素的索引值，返回结果
var StockSpanner = function() {
this.data = []
this.stack = []
};
// 使用单调栈
StockSpanner.prototype.next = function(price) {
var arr = this.data
var stack = this.stack
arr.push(price)
var i = arr.length
// 保存一个递增栈，当插入新元素时，与栈顶元素做比较并依次弹出，找到第一个大于当前元素的索引值，返回结果
while(stack.length && arr[stack[stack.length - 1]] <= price){
stack.pop()
}
var ans = i - (stack.length ? stack[stack.length - 1] + 1 : 0)
stack.push(i-1)
return ans
};
// 输入 [100, 80, 60, 70, 60, 75, 85]
// 输出 [1, 1, 1, 2, 1, 4, 6]
// [100] [100, 80] [100, 80, 60] [100, 80, 70] [100,80,60] [100,80,75] [100,85]3. 小结
本文主要总结了单调栈的概念和一些应用场景，大致了解了利用单调栈来解决求前后较大值、较小值的一些方法。