type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
有一类问题需要维护一段区间内的最大值或最小值，例如
滑动窗口、区间最值等问题。一般情况下，我们可以使用线段树、ST表等数据结构来解决这类问题，但是这些数据结构的实现较为复杂，需要一定的时间和精力来学习和掌握。而单调队列则是一个简单而高效的数据结构，可以用来解决这类问题。基本概念
单调队列是一种存储数据的队列，其中元素的顺序是单调递增或单调递减的。在算法竞赛中，我们一般使用两个单调队列，一个维护单调递增序列，另一个维护单调递减序列。
单调队列是一个双端队列。
单调队列的应用：
滑动窗口
滑动窗口是一类问题，需要在一个长度为n的序列中，找到所有长度为k的连续子序列中的最大值或最小值。使用单调队列可以在O(n)的时间复杂度内解决该问题。
具体做法如下：
- 首先，将前k个元素插入单调队列中，并记录队列的最大值或最小值。
- 然后，从第k+1个元素开始，每次将一个新的元素插入单调队列中。
- 插入时，先将队列中所有小于等于该元素的队尾元素出队，保证队列中的元素单调递减。
- 然后，将该元素插入队尾，并记录队列的最大值或最小值。
- 最后，将长度为k的子序列的最大值或最小值输出即可。
区间最值
需要在一个长度为n的序列中，找到所有长度为k的子序列中的最大值或最小值。使用单调队列可以在O(n)的时间复杂度内解决该问题。
其实现方法与上面类似，但是需要注意：
- 区间最值问题是在不限制子序列连续性的情况下，找到子序列中的最大值或最小值。
- 而滑动窗口问题则是在限制子序列必须连续的情况下，找到所有长度为k的子序列中的最大值或最小值。
154. 滑动窗口
题目要求：给你一段长度为n的序列，并且给你一个k，使得你维护一个长度为k的子序列，并且找到整个序列中全部长度为k的子序列的所有的最小值与最大值。
示例：
结果如下：
如果我们在使用两重for循环，如下所示：
这样每次都重复枚举新的i的位置，并且找到其对应窗口的最大值与最小值，则时间复杂度为O（nk）。我们可以使用单调队列使得时间复杂度降低为O（nlogn）：
单调队列的过程如下：以维护滑动窗口内的最大值为例
head：单调队列头 ；tail：单调队列尾
q：单调队列存储数组，nums：原数组
k=3
注意我们的单调队列存储的是元素nums[i]的下标i
首先head与tail初始化为0（下标1表示起始元素）
- i=1，元素 1 ：此时队列为空，直接插入单调队列的尾部，tail++，此时
head=0，tail=1，q： 1
- i=2，元素 3 ：此时队列非空，可以注意到队尾元素 1 小于3，因为我们的单调队列维护最大值，所以会删除队尾元素，一直到待插入元素小于队尾元素才行，或者队列为空，tail--，然后我们找到了合适的位置，则元素 3 插入到单调队列的尾部，++tail；由于我们先出再入，此时
head=0，tail=1，q：2
- i=3，元素 -1：此时队列非空，并且待插入元素小于队尾元素，直接插入到尾部，tail++，并且此时枚举到的元素下标为 i= 3 ，此时正好是第一个长度为k的窗口，因此 head++。此时
head=1，tail=2，q：2 -1。输出队头元素：nums[q[head]]=nums[q[1]]=nums[2]=3
- i=4，元素 -3：此时队列非空，并且待插入元素小于队尾元素，直接插入到尾部，tail++，此时
head=1，tail=3，q：2 3 4。输出队头元素：nums[q[head]]=nums[q[1]]=nums[2]= 3
- i=5，元素 5 ：此时队列非空，可以注意到队尾元素小于待插入元素，所以队尾元素出队，一直到待插入元素小于队尾元素才行，或者队列为空，此时我们找到了合适的位置，则元素 5 插入到单调队列的尾部；经过了很多次的tail--后，然后++tail，此时
head=1，tail=1，q：5。输出队头元素：nums[q[head]]=nums[q[1]]=nums[5]=5
- i=6，元素 3：此时队列非空，并且待插入元素小于队尾元素，直接插入到尾部，tail++，此时
head=1，tail=2，q：5 6。输出队头元素：nums[q[head]]=nums[q[1]]=nums[5]=5
- i=7，元素 6 ：此时队列非空，可以注意到队尾元素小于待插入元素，所以队尾元素出队，一直到待插入元素小于队尾元素才行，或者队列为空，此时我们找到了合适的位置，则元素 6 插入到单调队列的尾部；经过了很多次的tail--后，然后++tail，此时
head=1，tail=1，q：7。输出队头元素：nums[q[head]]=nums[q[1]]=nums[7]=6
- i=8，元素 7 ：此时队列非空，可以注意到队尾元素小于待插入元素，所以队尾元素出队，一直到待插入元素小于队尾元素才行，或者队列为空，此时我们找到了合适的位置，则元素 7 插入到单调队列的尾部；经过了很多次的tail--后，然后++tail，此时
head=1，tail=1，q：8。输出队头元素：nums[q[head]]=nums[q[1]]=nums[8]=7
可以注意到几个问题？
- 我们在单调队列中存储的是原数组的下标值，这样便于找到原始数据以及对队列进行操作
- q[head] 表示 队头元素，这个元素是一个下标，通过nums[q[head]]就可以找到队头的真正数据。
- tail什么时候变我们都知道，但是什么时候
head会变？ - 当队头元素小于 i-k+1的时候。 i为窗口右端点时，i-k+1表示左端点，队头元素表示的是下标，也就是说当
队列队头元素小于窗口的左端点时，说明这个窗口已经超过了，不包含队头元素了，因此需要移动head到窗口的新的左端点位置，head++。
- 什么时候输出区间最大值？
- 当遍历下标 i>k-1的时候。k-1表示窗口的最小保持长度，例如 k=3，k-1=2，因此当 i=3的时候，i>k-1，那么表示我们正处于第一个窗口的位置（i=3，窗口包括i=1，2，3位置的元素），那么我们输出队头元素所代表的元素值。往后每遍历一个i，都需要输出一次队头，因为每次都是一个长度为k的子窗口。
同理使用STL的deque也可以实现，因为deque本身就是一个双端队列。
135. 最大子序和
题目要求：给你一个序列，在长度不超过m的情况下，找到所有长度不超过m的子序列的和的最大值是多少。
示例：
m=4，可以得到最后四个数字的和最大，并且长度为4，不超过m，满足。
一看到子序列的区间和我们就可以想到前缀和。
因此这道题目第一个任务就完成了，我们只需要求出前缀和，并且计算在长度不超过m的情况下：
- 计算sum[i]-sum[j-1]的最大值
其中 i为m长度子序列的右端点，j为左端点，因此sum[i]-sum[j-1]表示的就是这段区间的和。
那么现在问题来了，我们如果求得者每个这样的区间的最大值呢，可以使用O（N^2）枚举所有的子区间，然后分别计算他们的最大值，不过这样做显然是超时的。
观察这个式子：要想使得sum[i]-sum[j-1]最大，因此我们不妨固定住右端点i。
然后在 [i-m+1，i] 的范围内找到一个最小的前缀和使得 sum[j-1]最小，这样就可以让 sum[i]-sum[j-1]最大。
因此问题就转换为了在 [i-m+1，i]区间内维护一个区间最小值，然后每次
更新右端点 i 的时候直接计算sum[i]-sum[j-1]即可，其中 j 的位置就是前缀和最小值的位置因此我们可以使用单调队列维护滑动窗口最小值.
维护最小值：
- 入队的操作：如果队列为空，则插入到队列尾；如果队尾元素大于待插入元素，则弹出队尾元素，一直到队尾元素小于待插入元素位置。
- 出队的操作：当队头超过了长度为 m 的窗口的范围，即q[head]在i-m+1的左边，head++
需要注意的点：
- 出队的时候我们的head需要指向窗口左端点的前一个，因为我们的前缀和的计算是 sum[i]-sum[j-1]，j的位置就是左端点的位置。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/ad326204-9180-4e44-af85-eac8b5df9f84
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。