贰.1.3 单调栈

贰.1.3.1 定义

单调栈,顾名思义就是栈内元素单调按照递增(递减)顺序排列的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。

示例:用数组[7,4,9,5,3,2]构建一个单调递增栈。

代码示例:

(()=>{
let A=[7,4,9,5,3,2],stk=[];
let l=A.length;
for (let i = 0; i < l; i++) {
while (stk.lenght && A[i] > A[stk[stk.length-1]]) { // 单调递增栈
// 单调递减栈的情况为 A[i] < A[stk[stk.length-1]]]
stk.pop();
}
stk.push(i);
}
})();

贰.1.3.2 应用场景

  • 找出数组中每项左/右边第一个大于/小于它的解;

  • 题目中隐含查找第一个(或离此项元素最近的)大于/小于此项元素的值,这类问题都可以考虑用单调栈求解。

贰.1.3.3 应用示例

1.气温问题(LeetCode.739

题目如下:

根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个数组T= [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是[1, 1, 4, 2, 1, 1, 0, 0]

解法一

这道题用若2个暴力循环的办法解决,时间复杂度是 O(N2)O(N^2)

/**
* @param {number[]} T
* @return {number[]}
*/
var dailyTemperatures = function (T) {
let arr = [];
let l = T.length;
for (let i = 0; i < l; i++) {
if (i == l - 1) {//末尾一定是0
arr.push(0);
} else {
for (let j = i + 1; j < l; j++) {
if (T[j] > T[i]) {
arr.push(j - i);
break;
}else if(j==l-1){
arr.push(0);
}
}
}
}
return arr;
};

解法二

而若使用单调栈,时间复杂度能将为 O(N)O(N) 。来分析下这道题,思路如下:

  • 维护一个单调递增栈,栈内存储气温数组 T 的 index ;

  • 查看当前元素是否大于栈顶元素所对应的 T 的值,也就是 T[stack[stack.length - 1]] ;

  • 如果大于,那说明找到需要等待的天数。如果不大于那说明还没到找到比这天高的温度,同时继续维护这个单调栈;

  • 如果大于,需要等待的天数就是当前数组 T 的index减去单调栈顶对应的index;

  • 若循环完毕还没有找到,则需要等待的天数为0。

/**
* @param {number[]} T
* @return {number[]}
*/
var dailyTemperatures = function(T) {
let { length } = T;
let res = new Array(length).fill(0);
let stack = [];
for(let i = 0; i < length; i++) {
while(stack.length && T[i] > T[stack[stack.length - 1]]) {
let index = stack.pop();//条件满足得到一个结果之后,取出栈顶存放的index
//并执行出栈,可以接着计算下一个了。
res[index] = i - index;//res[index]是巧妙之处,存放天数
}
stack.push(i);//栈内存放T的index
}
return res;
};

说白了就是空间换时间,新增一个单调栈存放index,巧妙地来换取时间复杂度的降低。

2.求数组项左右两侧比该项小的第一个数

原题如下:

给定一个长度为N的正整数数组,输出每个数组项左右两边第一个比它小的数,如果不存在则输出 - 1。 输入: [3, 4, 2, 7, 5]

输出: 左边 [-1, 3, -1, 2, 2] 右边 [2, 2, -1, 5, -1]

解题思路:

  • 用一个单调栈存放数组项的index;

  • 用两个数组存放两侧输出结果;

  • 栈顶(对应的数组项)右边第一个更小的元素是即将入栈的当前元素;

  • 数组当前项左边的第一个更小的元素,是栈顶元素(对应的数组项)。

((arr) => {
let l = arr.length;
let stack = [];
let resLeft = new Array(l).fill(-1);
let resRight = new Array(l).fill(-1);
for (let i = 0; i < l; i++) {
while (stack.length && arr[i] < arr[stack[stack.length - 1]]) {
let index = stack.pop();
resRight[index] = arr[i];
if (stack.length)
resLeft[index] = arr[stack[stack.length - 1]];
}
stack.push(i);
}
console.log(resLeft, resRight);
})([3, 4, 2, 7, 5]);

贰.1.3.4 总结要点

单调栈的核心并不是单调,单调递增或者递减只不过是副产品。其实际意义在于:

  • 实际上单调栈中并不保存数组项的值,而是保存数组项在原数组中的索引位置(index),它把空间复杂度从O(1)增大为O(N);

  • 因为针对单调栈又做了一遍历子循环(while),结合出栈操作,这个循环内可以巧妙地做很多事情;由此,单调栈成为一个临时用来协助降低时间复杂度的数据结构,;

  • 若从1到N遍历数组一遍,把每个将要放入的数组项其对应的索引位置(index)记录到栈里,就可以在O(N)的时间复杂度内得到数组所有项的左/右边、距离该项元素最近、且比该项元素大/小的其他元素的索引位置(index)。