对不起，掌握这些单调栈的知识后，我有点飘

小鱼儿 2023-01-06 05:35 111阅读 0赞

今天我们好好说说**单调栈和单调队列**。其实很容易理解，单调栈就是栈内单调递增或单调递减的栈，栈内元素是有序的，单调队列同样也是。

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

![format_png][]

提纲

## 单调队列 ##

### 剑指 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

![format_png 1][]

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

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

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

我们来对视频进行解析

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

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

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

#### 题目代码： ####

![format_png 2][]

### 239.滑动窗口最大值 ###

#### 题目描述： ####

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

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

**示例1：**

> 输入：nums = \[1,3,-1,-3,5,3,6,7\], k = 3 输出：\[3,3,5,5,6,7\]

#### 题目解析： ####

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

![format_png 3][]

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

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

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

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

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

![format_png 4][]

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

![format_png 5][]

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

![format_png 6][]

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

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

6.返回数组

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

#### 题目代码 ####

![format_png 7][]

## 单调栈 ##

### 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() 函数则直接返回变量保存的值即可。下面我们来看一下我们借助辅助栈，如何解决这个题目吧。

![format_png 8][]

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

我们来对视频进行解析

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

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

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

#### 题目代码 ####

![format_png 9][]

### 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，这个题目用到的是**单调栈**的思想，下面我们来看一下视频解析。

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

![format_png 10][]

### 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的例子进行举例，他的雨水到底代表的是什么。输入代表的是黄色箱子的个数，蓝色箱子代表雨水数量。缝隙之间可以装多少水

![format_png 11][]

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

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

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

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

![format_png 12][]

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

**注：能接到水的情况，肯定是中间低两边高的情况**

![format_png 13][]

因为我们需要维护一个单调栈，所以我们则需要将0出栈1入栈，那么此时栈内元素为4，3，2，1。下一位元素为1，我们入栈，此时栈内元素为4，3，2，1，1。

下一元素为5，栈顶元素为1，栈顶的下一元素仍为1，则需要再下一个元素，为2，那我们求当前层接到的水的数量。

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

![format_png 14][]

我们是通过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这三个元素同样也可以接到水。

![format_png 15][]

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

![format_png 16][]

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

### 题目代码： ###

![format_png 17][]

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

最后，点赞还是要求一下的，万一屏幕前的大帅比和大漂亮就点了呢？

[format_png]: /images/20221119/eef3d082dc794f5bb1eea656d81eb18f.png
[format_png 1]: /images/20221119/87a3f6fb423c41ea87b3c36ecf2bc4c6.png
[format_png 2]: /images/20221119/da5535f1817a48dca739775994db537b.png
[format_png 3]: /images/20221119/537ed17782c44b4d88ac449205ea1d26.png
[format_png 4]: /images/20221119/7ebb0317f33541f194b3d4dc8cc71211.png
[format_png 5]: /images/20221119/35af0e42946d474eb57acc07026bce90.png
[format_png 6]: /images/20221119/200c45e2181047aca850ee594e98b807.png
[format_png 7]: /images/20221119/f871ab65373f46cfb87bf15df3872d92.png
[format_png 8]: /images/20221119/5c47e5371d65431c8c919607f2d3f453.png
[format_png 9]: /images/20221119/50c3bc76b5c3428e9b479022d534abcd.png
[format_png 10]: /images/20221119/ea50a3b365d6428681cf801359589da8.png
[format_png 11]: /images/20221119/b8c54310e0ef4e4f95463b4e7d1362a2.png
[format_png 12]: /images/20221119/e957226411814266930a52ff086001f2.png
[format_png 13]: /images/20221119/6736ba3746454779a475a707ffefe39f.png
[format_png 14]: /images/20221119/ba4c95ec750e48dbb44f8df089729d82.png
[format_png 15]: /images/20221119/f6c587f6a1664a8ea899bfb0ee892d93.png
[format_png 16]: /images/20221119/cb7bf246be144524a92a831f6c2fc226.png
[format_png 17]: /images/20221119/ac74a11289a44f938db59eeafe11b709.png