袁厨携袁记菜馆全体工作人员祝大家在新的一年，健健康康，开开心心。发量暴增，钱包超大。
哎，元旦假期结束了，又要继续搬砖了，我们接着做题吧，今天我们好好说说单调栈和单调队列。其实很容易理解，单调栈就是栈内单调递增或单调递减的栈，栈内元素是有序的，单调队列同样也是。
下面我们通过几个题目由浅入深，一点一点挖透他们吧！
提纲
请定义一个队列并实现函数 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.入队时，我们需要维持一个单调递减的双端队列，因为我们需要确保队头元素为最大值嘛。
给你一个整数数组 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.返回数组
是不是一下就搞懂啦。你真帅，下面我们来看一下代码吧。
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
输入：
["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 的最小元素
题目描述：
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 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，这个题目用到的是单调栈的思想，下面我们来看一下视频解析。
注：栈中的括号内的值，代表索引对应的元素，我们的入栈的为索引值，为了便于理解将其对应的值写在了括号中
这道接雨水也是一道特别经典的题目，一道必刷题目，我们也用单调栈来解决。下面我们来看一下题目吧
给定 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
好啦，咱们的单调队列和单调栈的题目到这里就算总结完毕啦，希望对你能有一点点帮助。
树莓派Pico：仅4美元的MCU
嵌入式Linux开发板裸机程序烧写方法总结
国产16位MCU的痛点，可以用这款物美价廉产品
