算法通关（2）--单调队列

特点：

队列中的元素保持单调递增或者单调递减的顺序
可以在头部和尾部进行元素的插入和删除操作
大小是动态变化的，由元素的入队和出队的操作决定

单调队列的经典用法

1.维持窗口滑动中的最大/最小值

维持了一个依次称为最大值的可能性！

增加数字的逻辑：维持滑动窗口的最大值，构建递减的队列例如：[5 2 4 6 7 1]:当0位置的5从尾部进队列（max=5）,1位置的2进入队列（max=5）,2位置的4进入队列前，弹出1位置的2，（为什么弹出？因为他再也没有机会称为最大值了！！！）2位置的4进入，(max=5),3位置的6进入前，弹出2位置的4，0位置的5，(max=6),4位置的7进入前，弹出4位置的6，(max=7),5位置的1直接进。

减少数字的逻辑：从头部进行弹出，相当于从左边突出数字，用L++进行维护，可以说这个下标过期了，那么这就可以解释形如[5,3,5,1]当2位置的5进行加入队列时，0位置的5进行弹出。（下标比0大，就是晚过期，比下标为0的位置晚弹出，因此为头部）

例1：板子题

. - 力扣（LeetCode）

维持一个长度为k-1的队列，当算最大值时，R++，算完后，L++，还是k-1长度。由于最大值在头部，直接使用头部的最大值，当头部使用过后，进行释放

int MAXN = 10001;
deque<int> d(MAXN);
int head = 0;
int tail = 0;
// 单调队列里存储的是下标！！！
vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();// 形成长度为 k - 1 的窗口for (int i = 0; i < k - 1; i++) {// 弹出 -- 滑动窗口有长度（尾巴 > 头），进的数大于队列的数while (head < tail && nums[d[tail - 1]] <= nums[i]) {tail--;}d[tail++] = i;}int m = n - k + 1;	// 结果数组的长度vector<int>ans(m, 0);// 当前窗口为k - 1// 当前窗口创建左右指针，为了找最大值for (int l = 0, r = k - 1; l < m; l++, r++) {// 进来while (head < tail && nums[d[tail - 1]] <= nums[r]) {tail--;}// 吸收一个数d[tail++] = r;// 最大值在头部ans[l] = nums[d[head]];// 如果是过期下标，最大值在滑动窗口的左边界，释放头部if (d[head] == l) {head++;}}return ans;
}

例题2：

. - 力扣（LeetCode）

思路：维持一个头部是最大的单调递减队列，维持一个头部是最小的单调递增队列，以0作为起始下标出发，分别记录最大最小值，直到走到末尾，记录下满足条件（最大值-最小值的绝对值小于等于limit）的距离(当前位置的下标-起始下标)。ok后，以1作为起始下标出发，按照上面的规则，直到走大末尾，之后是以2位置。。。
代码1：C++中的STL库

deque<int> maxDeque;	// 队列头部是进队的最大值
deque<int> minDeque;	// 队列头部是进队的最小值
vector<int> num;bool ok(int limit, int number) {// 获取单调减和单调增队列的队头元素--最大最小值int max_1 = (!maxDeque.empty()) ? max(num[maxDeque.front()], number) : number;int min_1 = (!minDeque.empty()) ? min(num[minDeque.front()], number) : number;return max_1 - min_1 <= limit;
}void push(int r) {// 入队条件：空 or 队尾元素 大于 当前元素，因为是一个单调减队列，队头元素最大while (!maxDeque.empty() && num[maxDeque.back()] <= num[r]) {maxDeque.pop_back();}maxDeque.push_back(r);// 入队条件：空 or 队尾元素 小于 当前元素，因为是一个单调增队列，队头元素最小while (!minDeque.empty() && num[minDeque.back()] >= num[r]) {minDeque.pop_back();}minDeque.push_back(r);
}void pop(int l) {// 队列不空 + 队头是要弹出的数if (!maxDeque.empty() && maxDeque.front() == l) {maxDeque.pop_front();}if (!minDeque.empty() && minDeque.front() == l) {minDeque.pop_front();}
}int longestSubarray(vector<int>& nums, int limit) {maxDeque.clear();minDeque.clear();	// 清空队列num = nums;			// 为了少传参int n = nums.size();int ans = 0;for (int l = 0, r = 0; l < n; l++) {// 不越界 + 队列算上推进去最大绝对值差<=limit才能pushwhile (r < n && ok(limit, nums[r])) {push(r++);}// 越界 或者 最大绝对值差>limitans = max(ans, r - l);pop(l);	// 此位置算完了，弹出算下一位置}return ans;
}int main() {vector<int> nums = { 10,1,2,4,7,2 };int limit = 5;int length = longestSubarray(nums, limit);cout << length;return 0;
}

代码2：数组的模拟实现

const int MAXN = 10001;
int maxQueue[MAXN];		// 队头元素最大 -- 递减
int minQueue[MAXN];		// 队头元素最小 -- 递增
int maxHead, minHead, maxTail, minTail;	// 两个队列的头和尾
vector<int>num;	// 将nums变成全局变量bool reach(int limit, int value) {// 加入右边的数字，看是否<=limit// 如果此时窗为空，那么最大值就是进来的数int maxValue = (maxHead < maxTail) ? max(num[maxQueue[maxHead]], value) : value;int minValue = (minHead < minTail) ? min(num[minQueue[minHead]], value) : value;return maxValue - minValue <= limit;
}void pushValue(int r) {// 加入+调整// 不为空+进的大于队尾元素，弹出while (maxHead < maxTail && num[maxQueue[maxTail - 1]] <= num[r]) {maxTail--;}maxQueue[maxTail++] = r;// 不为空+进的小于队尾元素，弹出while (minHead < minTail && num[minQueue[minTail - 1]] >= num[r]) {minTail--;}minQueue[minTail++] = r;
}void popValue(int l) {// 不为空+是要弹出的元素if (maxHead < maxTail && maxQueue[maxHead] == l) {maxHead++;}if (minHead < minTail && minQueue[minHead] == l) {minHead++;}
}int longestSubarray(vector<int>& nums, int limit) {maxHead = minHead = maxTail = minTail = 0;	// 清空队列num = nums;									// 减少传参int n = nums.size();int len = 0;for (int l = 0, r = l; l < n; l++) {// 创建窗口[l,r),r是没有进入窗口的，下一个位置// 不能越界，r位置的数进来是否达标，即<=limitwhile (r < n && reach(limit, num[r])) {		pushValue(r++);}// [l,r) 以l开头子数组向右延伸的最大范围len = max(len, r - l);// 这个l弄完了，弹出popValue(l);}return len;
}int main() {int n, x, limit;scanf("%d", &n);vector<int> nums;for (int i = 0; i < n; i++) {scanf("%d", &x);nums.push_back(x);}scanf("%d", &limit);int res = longestSubarray(nums, limit);printf("%d", res);return 0;
}

相似题目：[USACO12MAR] Flowerpot S - 洛谷

例3：

862. 和至少为 K 的最短子数组 - 力扣（LeetCode）

思路：满足条件的子数组可以以任意下标结尾，可能以5下标结尾的子数组满足条件的有两个，那么我们就取最短的。这样子的大体思路出来了。以每个位置下标的数字结尾，向前数最短的满足条件的长度，总的最短长度就是题目的要求。
但是求最短长度需要求得一个区间的和，如何快速求得区间的和？对的，利用前缀和，求得数组每个位置的前缀和，当求得每一段数组的和时，就可以使对应位置的和相减即为相对应区间长度的和。由此可以得出这样的两段代码：

// 求前缀和
for (int i = 0; i < n; i++) {preSum[i+1] = preSum[i]+nums[i];
}// 当前的前缀和 - 头部前缀和 大于等于 k，达标
while (head != tail && preSum[i] - preSum[Queue[head]] >= k) {ans = min(ans, i - Queue[head++]);
}

添加前缀和的注意情况：构建一个头为最小值的单调队列，单调队列中放前缀和。为什么这样子的构造。举个例子:数组[6,5,4,-3,4...]要满足的和为20，数组此时构成的前缀和为[6,11,15,12,16....]当后面的前缀和减去12时得到的值一定大于减去15的值，更加的接近20，而且减去12得到的数组长度还短，那为什么不选择减去12呢~~

淘汰的情况：[1,2,1,6,7,2,1,5,3],前缀和:[1,2,4,10,17,19,20,25,28]，假设要满足子序列和12，前缀和1，2，4，10进入，当17进入是满足条件，而且淘汰掉1和2得到的和为14，也满足条件，长度为3，比原先的长度为5要短，加入前缀和17... 算最短的长度

总体：例子：[5,3,2,-4,7,3,10],构建头部最小的单调递增栈。

int n, k;
const int MAXN = 100005;
long preSum[MAXN];	// 前缀和
int head, tail;
int Queue[MAXN];	// 构建递增队列
int shortestSubarray(vector<int>& nums, int k) {int n = nums.size();// 求前缀和for (int i = 0; i < n; i++) {preSum[i+1] = preSum[i]+nums[i];}head = tail = 0;int ans = INT_MAX;for (int i = 0; i <= n; i++) {// 当前的前缀和 - 头部前缀和 大于等于 k，达标while (head != tail && preSum[i] - preSum[Queue[head]] >= k) {ans = min(ans, i - Queue[head++]);}// 构建单调递增队列，放前缀和while (head!=tail && preSum[Queue[tail - 1]] >= preSum[i]) {tail--;}Queue[tail++] = i;}return ans != INT_MAX ? ans : -1;
}