深入浅出搞通单调队列单调栈

2021/07/23 17:20
阅读数 118

袁厨携袁记菜馆全体工作人员祝大家在新的一年,健健康康,开开心心。发量暴增,钱包超大。

哎,元旦假期结束了,又要继续搬砖了,我们接着做题吧,今天我们好好说说单调栈和单调队列。其实很容易理解,单调栈就是栈内单调递增或单调递减的栈,栈内元素是有序的,单调队列同样也是。

下面我们通过几个题目由浅入深,一点一点挖透他们吧!

提纲

单调队列

剑指 Offer 59 - II. 队列的最大值

题目描述:

请定义一个队列并实现函数 max_value 得到队列里的最大值

若队列为空,pop_front 和 max_value 需要返回 -1

示例 1:

输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]

[[],[1],[2],[],[],[]] 

输出: [null,null,null,2,1,2]

示例 2:

输入: 

["MaxQueue","pop_front","max_value"] 

[[],[],[]] 

输出: [null,-1,-1]

题目解析:

我们先来拆解下上面的示例 1


其实我觉得这个题目的重点在理解题意上面,可能刚开始刷题的同学,对题意理解不够透彻,做起来没有那么得心应手,通过上面的图片我们简单了解了一下题意,那我们应该怎么做才能实现上述要求呢?

下面我们来说一下双端队列。我们之前说过的队列,遵守先进先出的规则,双端队列则可以从队头出队,也可以从队尾出队,不用遵守先进先出的规则,我们先通过一个视频来简单了解下双端队列。



我们可以用双端队列做辅助队列,用辅助队列来保存当前队列的最大值。我们同时定义一个普通队列和一个双端单调队列。普通队列就正常执行入队,出队操作。max_value 操作则返回咱们的双端队列的队头即可。下面我们来看一下代码的具体执行过程吧。



我们来对视频进行解析

1.我们需要维护一个单调双端队列,上面的队列则执行正常操作,下面的队列队头元素则为上面队列的最大值

2.出队时,我们需要进行对比两个队列的队头元素是否相等,如果相等则同时出队,则出队后的双端队列的头部仍为上面队列中的最大值。

3.入队时,我们需要维持一个单调递减的双端队列,因为我们需要确保队头元素为最大值嘛。

题目代码:

239.滑动窗口最大值

题目描述:

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7]

题目解析:

题目让我们找出每个滑动窗口的最大值,那么题目具体含义是怎样呢?


就是为了让我们输出每个窗口的最大值,那我们思考一下,我们一个数组一共有多少窗口呢?

比如我们这个例子中,我们的窗口长度为 3 ,数组长度为 8,我们的窗口每次移动一位,所以我们一共有 8 - (3 - 1)也就是  8 - 3 + 1。所以我们返回数组的长度是跟原数组长度和滑动窗口的长度有关的。

也就是 winlen =  len(数组长度) - k(滑动窗口长度) + 1。下面我们来看一个视频,相信通过这个视频,大家一下就能搞懂啦。



下面我们对视频进行拆解。

1.先将我们第一个窗口的所有值按照规则存入单调双端队列中,单调队列里面的值为单调递减的。如果发现队尾元素小于要加入的元素,则将队尾元素出队,直到队尾元素大于等于新元素时,再让新元素入队,目的就是维护一个单调递减的队列。第一个窗口的所有值入队之后情况,如下图。是因为 3 要入队时,此时队中有 1 ,不能保证单调递减,所以需要 1 出队,然后 3 入队, -1  入队时,队中有 3 ,满足单调,所以  -1  可以入队。


2.我们将第一个窗口的所有值,按照单调队列的规则入队之后,因为队列为单调递减,所以队头元素必为当前窗口的最大值,则将队头元素添加到数组中。


3.移动窗口,判断当前窗口前的元素是否和双端队列队头元素相等,如果相等则出队,此时滑动窗口的最大值发生改变了。


4.继续然后按照规则进行入队,维护单调递减队列,这里和第一条规则一致。

5.每次将队头元素存到返回数组里。

6.返回数组

是不是一下就搞懂啦。你真帅,下面我们来看一下代码吧。

题目代码


单调栈

leetcode 155 最小栈

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

输入:

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]

输出:

[null,null,null,null,-3,null,0,-2]

题目解析

感觉这个题目的难度就在读懂题意上面,读懂之后就没有什么难的了,我们在上面的滑动窗口的最大值已经进行了详细描述,其实这个题目和那个题目思路一致。

该题让我们设计一个栈,该栈具有的功能有,push,pop,top等操作,并且能够返回栈的最小值。比如此时栈中的元素为 5,1,2,3。我们执行 getMin()  ,则能够返回 1。这块是这个题目的精髓所在,见下图, 这个题目也可以不利用辅助栈解决,但是不符合本文主题,所以在这里先不进行详细描述。大致思路为,把当前最小值用一个变量保存,需要入栈的值小于当前最小值时,先把当前最小值入栈,再将需要入栈的值入栈,并更新当前最小值。如果大于当前最小值,则直接入栈。getMin() 函数则直接返回变量保存的值即可。下面我们来看一下我们借助辅助栈,如何解决这个题目吧。


我们一起先通过一个视频先看一下具体解题思路,通过视频一定可以整懂的,我们注意观察栈 B 内的元素。



我们来对视频进行解析

1.我们执行入栈操作时,先观察需要入栈的元素是否小于栈 B 的栈顶元素,如果小于则两个栈都执行入栈操作。

2.栈 B 的栈顶元素则是栈 A 此时的最小值。则 getMin() 只需返回栈 B 的栈顶元素即可。

3.出栈时,需要进行对比,若栈 A 和栈 B 栈顶元素相同,则同时出栈,出栈后B 的栈顶保存的仍为此时栈 A 的最小元素

题目代码


leetcode 739 每日温度

题目描述:

请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例1:

输入:temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

输出:arr =   [1, 1, 4, 2, 1, 1, 0, 0]

示例2:

输入:temperatures = [30,30,31,45,31,34,56]

输出:arr =   [2,1,1,3,1,1,0]

题目解析

其实我们可以换种方式理解这个题目,比如我们 temperatures[0] = 30,则我们需要找到后面第一个比 30 大的数,也就是 31,31的下标为 2,30 的下标为 0 ,则我们的返回数组 arr[0] = 2。理解了题目之后我们来说一下解题思路。

遍历数组,数组中的值为待入栈元素,待入栈元素入栈时会先跟栈顶元素进行对比,如果小于等于该值则入栈,如果大于则将栈顶元素出栈,新的元素入栈。

例如栈顶为69,新的元素为72,则69出栈,72入栈。并赋值给 arr,69 的索引为4,72的索引为5,则 arr[4] = 5 - 4 = 1,这个题目用到的是单调栈的思想,下面我们来看一下视频解析。



注:栈中的括号内的值,代表索引对应的元素,我们的入栈的为索引值,为了便于理解将其对应的值写在了括号中



leetcode 42 接雨水

这道接雨水也是一道特别经典的题目,一道必刷题目,我们也用单调栈来解决。下面我们来看一下题目吧

题目描述:

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。


示例1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出:6

示例2:

输入:height = [4,2,0,3,2,5]

输出:9

示例2:

输入:[4,3,2,0,1,1,5

输出:13

题目解析:

看了上面的示例刚开始刷题的同学可能有些懵逼,那我们结合图片来理解一下,我们就用示例3的例子进行举例,他的雨水到底代表的是什么。输入代表的是黄色箱子的个数,蓝色箱子代表雨水数量。缝隙之间可以装多少水

说明:上面是由数组 [4,3,2,0,1,1,5]表示的高度图,在这种情况下,可以接 13个单位的雨水(见下图)。

上图则为我们的题目描述,是不是理解了呢?你也可以这样理解我们在地上放置了若干高度的黄色箱子,他们 中间有空隙 ,然后我们想在他们里面 插入若干蓝色箱子 ,并保证插入之后,这些箱子的左视图和右视图都不能看到蓝色箱子。

好啦题目我们已经理解了,下面我们来看一下接雨水问题到底该怎么做,其实原理也很简单,我们通过我们的例3来进行说明。

首先我们依次入栈4,3,2,0我们的数组前四个元素是 符合单调栈规则 的。但是我们的第五个1,是大于0的。那我们就需要0出栈1入栈。但是我们这样做是为了什么呢?有什么意义呢?别急我们来看下图。

上图我们的,4,3,2,0已经入栈了,我们的另一个元素为1,栈顶元素为0,栈顶下的元素为2。那么我们在这一层接到的雨水数量怎么算呢?2,0,1这三个元素可以接住的水为一个单位(见下图)这是我们 第一层接到水的数量

注:能接到水的情况,肯定是中间低两边高的情况


因为我们需要维护一个单调栈,所以我们则需要将0出栈1入栈,那么此时栈内元素为4,3,2,1。下一位元素为1,我们入栈,此时栈内元素为4,3,2,1,1。
下一元素为5,栈顶元素为1,栈顶的下一元素仍为1,则需要再下一个元素,为2,那我们求当前层接到的水的数量。

注:栈内保存的应是索引值,这里为了便于理解用了value值


我们是通过2,1,1,5这四个元素求得第二层的接水数为1*3=3;1是因为min(2-1,5-1)=min(1,4)得来的,大家可以思考一下 木桶效应 。装水的多少,肯定是按最短的那个木板来的,所以高度为1,3的话是因为5的索引为6,2的索引为2,他们之间共有三个元素(3,4,5)也就是3个单位。所以为6-2-1=3。
将1出栈之后,我们栈顶元素就变成了2,下一元素变成了3,那么3,2,5这三个元素同样也可以接到水。


这是第三层的接水情况,能够接到4个单位的水,下面我们继续出栈2,那么我们的4,3,5仍然可以接到水啊。

这是我们第四层接水的情况,一共能够接到5个单位的水,那么我们总的接水数加起来,那就是1+3+4+5=13。你学会了吗?别急还有动图我们,我们再来深入理解一哈。

题目代码:



好啦,咱们的单调队列和单调栈的题目到这里就算总结完毕啦,希望对你能有一点点帮助。

我个人认为像那种,思路不是特别好想,或者即使想到思路,编码时思考不细致容易出错的题目,才是最能提高我们编码能力的题目。所以我建了一个寒假刷题小队,就是以这种类型的题目为主。需要的同学可以点击咱们公众号的刷题小队进入。原创不易,欢迎各位对这个文章,点赞,在看,转发呀。


往期精选





本文分享自微信公众号 - sowhat1412(sowhat9094)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部