算法通关（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才能push
while (r < n && ok(limit, nums[r])) {
push(r++);
}
// 越界 或者 最大绝对值差>limit
ans = 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位置的数进来是否达标，即<=limit
while (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;
}