单调栈
单调栈方法主要用来处理例如数组左边第一个比它大的元素,右边第一个比它小的元素等等问题。
以Leetcode496为例,看一下思考方法。这道题实际上就是求数组中右边第一个比它大的元素,然后再用hash表映射一下,不要被两个数组迷惑了。
遇到这类问题首先考虑暴力做法,从前往后扫描每一个数组元素,再套一层循环,从当前元素后面开始扫描,找到一个比它大的。这种方法的复杂度是O(n^2)。现在考虑利用栈结构优化。
我们从后往前扫描,没遇到一个元素就把它入栈,并求出next greater number。考虑当轮到a[i]入栈的时候,它要从前往后扫描并找到第一个比它大的数,否则就为-1。在扫描过程中假设遇到a[i+k]<=a[i],考虑这a[i+k]这个元素是否会被后面的元素用到,也就是作为答案。答案是否定的。后面进来的元素它的前面已经有a[i]了,第一个比它大的元素肯定不会轮到a[i+k],所以这时可以直接把a[i+k]这个元素弹出。
代码如下
1 | class Solution { |
再来看一个拓展题leetcode503
这题要求循环搜索下一个更大元素,那其实可以把数组复制一份,接在后面。相当于我们求的事这个新数组的下一个更大元素,但实际下标还是在原数组内的(求余)。
代码如下
1 | class Solution { |
再来看一道题leetcode739每日温度。这是一道很经典的题,题解也有很多。
它其实也是要求下一个更大元素,但是求的是距离下一个更大元素要隔几天,所以这时栈里面存放的是数组的下标。
代码如下
1 | class Solution { |
单调队列
单调队列的思想也和单调栈差不多,也是先考虑暴力的场景,再看看使用队列之后有没有什么特殊的性质可以使得复杂度降为O(n)。运用的最多的就是滑动窗口方法。
以滑动窗口的最大值为例 剑指offer59
这题给定一个窗口的大小k,要求滑动窗口的最大值。暴力做法也很容易想到,两层循环,内层循环每次求扫描窗口内的最大值。这种做法的时间复杂度太低。考虑把窗口内元素入队来解决这个问题。
用i来表示当前将要入队的元素。如果队列中也就是窗口中前面的元素小于等于a[i],那么这个元素永远不可能是之后每个窗口的最大值,因为a[i]在队列中。所以可以一直从队尾弹出。(使用双端队列的结构)。直到遇到大于a[i]的元素,可以保证窗口中最大的元素始终位于队头。然后将i入队。
代码如下
1 | class Solution { |
还要注意判断当前队头元素是否已经滑出了窗口。