引言：
单调队列和单调栈都是一种数据结构，应用十分广泛，在蓝桥杯、ICPC、CCPC等著名编程赛事都是重点的算法，今天博主将自己对单调栈与单调队列的理解以及刷题的经验，用一篇博客分享给大家，希望对大家有所帮助，它们用于解决类似“寻找最大值与最小值”这样的问题。它们的区别在于如何维护数据的单调性。
- 单调栈（Monotonic Stack）：
- 单调栈是一种栈数据结构，只能在栈顶进行插入和删除操作。
- 单调栈的特点是栈中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
- 在插入新元素时，如果新元素破坏了当前的单调性，则从栈顶删除一部分元素，直到满足单调性要求。这样可以保证栈中的元素保持单调性。
- 单调栈的典型应用是在寻找下一个更大/更小元素的问题。
2.单调队列（Monotonic Queue）：
- 单调队列是一个双端队列，支持在队列两端进行插入和删除操作。
- 单调队列的特点是队列中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
- 在插入新元素时，如果新元素破坏了当前的单调性，则在队尾删除一部分元素，直到满足单调性要求。这样可以保证队列中的元素保持单调性。
- 单调队列的典型应用是在滑动窗口中寻找最大/最小值的问题。
单调队列和单调栈都是用于维护数据的单调性，但单调队列是双端队列，用于在滑动窗口中寻找最大/最小值，而单调栈是栈数据结构，用于寻找下一个更大/更小元素。
接上篇单调栈，下面我们对单调队列进行深度解析
单调队列：
单调队列是一种特殊的队列数据结构，用于解决一些与序列相关的问题。单调队列中的元素按照其值的大小有序排列，同时还满足队列的先进先出的性质。
单调队列的主要特点是，队列中的元素始终保持一个单调性，可以是递增或递减。这意味着，当有新的元素入队时，队列会自动进行调整，将不符合要求的元素删除。
单调队列的应用场景主要是解决滑动窗口相关的问题。滑动窗口是指在一个序列中，窗口以固定大小向右滑动，每次滑动一个位置。在每个滑动窗口中，需要对窗口中的元素进行一些操作。
使用单调队列可以在O(n)的时间复杂度内解决滑动窗口问题。具体的操作过程如下：
- 首先，将窗口的前k个元素依次入队；
- 与队列尾部的元素进行比较，将比当前元素小的元素从队列尾部依次出队，直到队列尾部的元素大于等于当前元素，或者队列为空；
- 判断队列的头部元素是否已经超出了滑动窗 口的范围，如果超出了，则将队列头部元素出队；
- 将当前元素入队；
- 对每个滑动窗口，都可以通过队列的头部元素获取到当前窗口的最大（最小）值。
总之，单调队列是一种高效解决滑动窗口问题的数据结构，它可以在O(n)的时间复杂度内完成操作。同时，单调队列也有一些其他的应用场景，如求滑动窗口中的最小值、最大值等。
如下图：滑动窗口为3，模拟单调队列入队可以一下过程。
单调队列是一种特殊的队列，它可以在 O(1) 时间内完成以下两种操作：
1. 在队尾插入元素 x。
2. 在队头删除元素。
单调队列常用于求解滑动窗口中的最值问题，例如求最大值、最小值或其他满足特定条件的值。
下面是一些单调队列的具体应用场景：
1. 求滑动窗口的最大值/最小值：给定一个数组 nums 和一个滑动窗口的大小 k，需要找出每个滑动窗口里的最大值或最小值。使用单调队列可以在 O(n) 时间内解决这个问题。
2. 求滑动窗口中的最大值与最小值的差值不超过一个给定值的个数：给定一个数组 nums、一个滑动窗口的大小 k，以及一个给定值 maxDiff，需要找出滑动窗口中最大值与最小值的差值不超过 maxDiff 的窗口个数。
3. 求滑动窗口中的最大子数组和：给定一个数组 nums 和一个正整数 k，需要找出滑动窗口中长度为 k 的连续子数组的最大和。
4. 求滑动窗口中的第 k 大的元素：给定一个数组 nums 和一个正整数 k，需要找出滑动窗口中第 k 大的元素。
这些是单调队列的应用场景之一，还有其他一些问题也可以使用单调队列解决。单调队列的核心思想是维护一个递增或递减的队列，通过在队尾插入元素和在队头删除元素来保持队列的单调性。这样就可以在 O(1) 时间内获取滑动窗口中的最值或其他满足条件的值。
模板奉上：
第一种使用STL
deque<int>q;//滑动窗口 for(int i = 0; i < nums.size(); i++){ while(!q.empty()&&nums[q.back()]<nums[i])//维护队列单调性（递增） q.pop_back(); q.push_back(i);//入队 if(!q.empty() && i-q.front() >= k)//判断队头是否需要出队 q.pop_front(); if(i >= k-1){ //在此处寻找最大值，以及代码扩展 res.push_back(nums[q.front()]);//取队头作为窗口最大元素 } } return res;
第二种自己手写一个
int h=-1,t=0; int q[1005]; vector<int> res; for(int i=0;i<nums.size();i++){ while(h<=t&&a[q[t]]<=nums[i])t--;//队尾不满足单调性出队 q[++t]=i;//入队 if(q[h]<i-k+1)h++;//队头超出窗口，出队 if(i-k+1>=0) res.push_back(nums[q[h]]);//此处代码扩展 } return res;
实战演练——单调队列习题
滑动窗口最大值
class Solution { public: vector<int> maxInWindows(vector<int>& nums, int k) { int q[100001]; int hh=0,tt=0; vector<int> ans; for(int i=0;i<nums.size();i++) { while(hh<=tt&&nums[q[tt]]<=nums[i]) tt--;//新元素不满足单调递增，队尾出队 q[++tt]=i;//新元素入队 if(q[hh]<i-k+1) hh++;//队头不再窗口内 if(i-k+1>=0) ans.push_back(nums[q[hh]]);//窗口内元素个数大于等于k，可进行操作 } return ans; } };
滑动窗口【模板】
#include<bits/stdc++.h> #define N 1000005 using namespace std; int n,k; int a[N]; deque<int> q;//使用双端队列 int main() { cin>>n>>k; for(int i = 1;i<=n;i++) cin>>a[i]; for(int i = 1;i<=n;i++)//求滑动窗口最小值 { while(q.size() && q.back()>a[i]) q.pop_back(); q.push_back(a[i]); if(i-k>=1 && q.front()== a[i-k]) q.pop_front(); if(i>=k) cout<<q.front()<<" "; } cout<<"\n"; q.clear();//清空防止影响求最大值 for(int i = 1;i<=n;i++)//求滑动窗口最大值 { while(q.size() && q.back()<a[i]) q.pop_back(); q.push_back(a[i]); if(i-k>=1 && q.front() == a[i-k]) q.pop_front(); if(i>=k) cout<<q.front()<<" "; } return 0; }
手写一个：
#include<iostream> using namespace std; const int N=1e6+5; int h,t; int n,k; int a[N],q[N]; int main(){ cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i]; } h=0,t=-1; for(int i=0;i<n;i++){ while(h<=t&&a[q[t]]>=a[i])t--; q[++t]=i; if(q[h]<i-k+1)h++; if(i-k+1>=0)cout<<a[q[h]]<<" "; } cout<<endl; h=0,t=-1; for(int i=0;i<n;i++){ while(h<=t&&a[q[t]]<=a[i])t--; q[++t]=i; if(q[h]<i-k+1)h++; if(i-k+1>=0)cout<<a[q[h]]<<" "; } return 0; }
多重背包问题（单调队列优化）
这里可以看一下我专门写的多重背包问题的博客，这里不再介绍
总结：
单调队列是一种非常有用的数据结构，可以高效地解决需要维护窗口内最值的问题。使用单调队列的时间复杂度为O(n)，其中n为输入数组的长度。其实现方式有双向队列和单调栈两种，根据具体问题的要求选择适合的实现方式即可，文章尚有不足，恳请各位大佬指出，博主不胜感激，感谢大家支持。
