贰.1.3 单调栈
贰.1.3.1 定义
单调栈,顾名思义就是栈内元素单调按照递增(递减)顺序排列的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。
示例:用数组[7,4,9,5,3,2]
构建一个单调递增栈。
代码示例:
贰.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个暴力循环的办法解决,时间复杂度是 ;
解法二
而若使用单调栈,时间复杂度能将为 。来分析下这道题,思路如下:
维护一个单调递增栈,栈内存储气温数组 T 的 index ;
查看当前元素是否大于栈顶元素所对应的 T 的值,也就是 T[stack[stack.length - 1]] ;
如果大于,那说明找到需要等待的天数。如果不大于那说明还没到找到比这天高的温度,同时继续维护这个单调栈;
如果大于,需要等待的天数就是当前数组 T 的index减去单调栈顶对应的index;
若循环完毕还没有找到,则需要等待的天数为0。
说白了就是空间换时间,新增一个单调栈存放index,巧妙地来换取时间复杂度的降低。
2.求数组项左右两侧比该项小的第一个数
原题如下:
给定一个长度为N的正整数数组,输出每个数组项左右两边第一个比它小的数,如果不存在则输出 - 1。
输入:
[3, 4, 2, 7, 5]
输出: 左边
[-1, 3, -1, 2, 2]
右边[2, 2, -1, 5, -1]
解题思路:
用一个单调栈存放数组项的index;
用两个数组存放两侧输出结果;
栈顶(对应的数组项)右边第一个更小的元素是即将入栈的当前元素;
数组当前项左边的第一个更小的元素,是栈顶元素(对应的数组项)。
贰.1.3.4 总结要点
单调栈的核心并不是单调,单调递增或者递减只不过是副产品。其实际意义在于:
实际上单调栈中并不保存数组项的值,而是保存数组项在原数组中的索引位置(index),它把空间复杂度从O(1)增大为O(N);
因为针对单调栈又做了一遍历子循环(while),结合出栈操作,这个循环内可以巧妙地做很多事情;由此,单调栈成为一个临时用来协助降低时间复杂度的数据结构,;
若从1到N遍历数组一遍,把每个将要放入的数组项其对应的索引位置(index)记录到栈里,就可以在O(N)的时间复杂度内得到数组所有项的左/右边、距离该项元素最近、且比该项元素大/小的其他元素的索引位置(index)。
最后更新于