单调队列
作用
维护区间最值（最大值，最小值）
操作
入队操作：队尾入队，将之前破坏单调性的元素移除
出队操作：如果队首元素超过区间范围，将队首元素移除
性质
元素性质：队首元素，永远维护区间最值（最大值，最小值）
均摊时间复杂度O(1):每个元素最多入队一次，出队一次，共2n次，均摊于每个元素2n/n=2
代码实现
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
void output(vector<int>arr,int n)
{
int len=0;
for(int i=0;i<n;i++)
len+=printf("%3d",i);
printf("\n");
for(int i=0;i<=len+1;i++)
printf("-");
printf("\n");
for(int i=0;i<n;i++)
printf("%3d",arr[i]);
printf("\n");
return ;
}
int main()
{
int n,k;//n为数组长度，k为窗口长度
cin>>n>>k;
deque<int>q;
vector<int>arr;
for(int i=1,a;i<=n;i++)//初始化数组
{
cin>>a;
arr.push_back(a);
}
output(arr,n);//输出数组
for(int i=0;i<n;i++)
{
while(!q.empty()&&arr[q.back()]>arr[i])q.pop_back();
//队列非空且队尾元素违反单调性则进行队尾出队
q.push_back(i);//新元素入队，存储的是下标不是值
if(i-q.front()==k)q.pop_front();//如果超过窗口则队首出队
printf("[%d,%d]:%d\n",max(0,i-k+1),i,arr[q.front()]);
}
return 0;
}单调栈
和单调队列相比扔掉了从头部出元素的操作
作用
维护最近大于或小于关系
谁把我弹出去，谁就是最近大于/小于我的元素
单调递增栈（维护最近小于关系）
单调递减栈（维护最近大于关系）
操作
入栈操作：入栈顶时将违反单调性的元素移除
代码实现
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
void output(vector<int>arr,int n)
{
int len=0;
for(int i=0;i<n;i++)
len+=printf("%3d",i);
printf("\n");
for(int i=0;i<=len+1;i++)
printf("-");
printf("\n");
for(int i=0;i<n;i++)
printf("%3d",arr[i]);
printf("\n");
return ;
}
int main()
{
int n;//数组长度
cin>>n;
vector<int>arr;
stack<int>s;
arr.push_back(-1);//左端
for(int i=0,a;i<n;i++)
{
cin>>a;
arr.push_back(a);
}
arr.push_back(-1);//右端
output(arr,arr.size());//输出数组
vector<int>l(arr.size());//存放左侧的最近小于关系
vector<int>r(arr.size());//存放右侧的最近小于关系
//求右侧的最近小于关系，正序入栈
for(int i=0;i<=arr.size()-1;i++)
{
while(!s.empty()&&arr[s.top()]>arr[i])
{
r[s.top()]=i;//若被弹出，则说明存在最近小于关系
s.pop();
}
s.push(i);
}
//求左侧的最近小于关系，逆序入栈
for(int i=arr.size()-1;i>=0;i--)
{
while(!s.empty()&&arr[s.top()]>arr[i])
{
l[s.top()]=i;//若被弹出，则说明具有最近小于关系
s.pop();
}
s.push(i);
}
for(int i=1;i<=n;i++)
{
printf("arr[%d]=%d,l[%d]=%d,r[%d]=%d\n",
i,arr[i],i,arr[l[i]],i,arr[r[i]]);
}
return 0;
}例题
1.滑动窗口
题目描述
给出一个长度为 N 的数组，一个长为 K 的滑动窗口从最左移动到最右，每次窗口移动，如下图：
找出窗口在各个位置时的极大值和极小值。
输入
第一行两个数 N,K。
第二行有 N 个数，表示数组中的元素。
输出
输出两行，第一行为窗口在各个位置时的极小值，第二行为窗口在各个位置时的极大值。
样例输入
8 3
1 3 -1 -3 5 3 6 7样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7代码实现
#include<iostream>
#include<deque>
using namespace std;
#define MAXSIZE 300000
int arr[MAXSIZE+5];
int min_item[MAXSIZE+5]={0};
int max_item[MAXSIZE+5]={0};
int main()
{
int n,k;
cin>>n>>k;
deque<int>q1,q2;//q1维护区间最小值，q2维护区间最大值
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=0;i<n;i++)
{
while(!q1.empty()&&arr[q1.back()]>arr[i])
{
q1.pop_back();
}
q1.push_back(i);
while(!q2.empty()&&arr[q2.back()]<arr[i])
{
q2.pop_back();
}
q2.push_back(i);
if(i>=k-1)
{
if(i-k==q1.front())q1.pop_front();
if(i-k==q2.front())q2.pop_front();
min_item[i]=arr[q1.front()];
max_item[i]=arr[q2.front()];
}
}
for(int i=k-1;i<n;i++)
{
printf("%d",min_item[i]);
if(i!=n-1)printf(" ");
}
cout<<endl;
for(int i=k-1;i<n;i++)
{
printf("%d",max_item[i]);
if(i!=n-1)printf(" ");
}
return 0;
}2.最大子序和
题目描述
输入一个长度为 n 的整数序列，从中找出一段不超过 M 的连续子序列，使得整个序列的和最大。
例如 1，−3,5,1，−2,3：
当 m=4 时，S=5+1−2+3=7；
当 m=2 或 m=3 时，S=5+1=6。
输入
第一行两个数 n,m。
第二行有 n 个数，要求在 n 个数找到最大子序和。
输出
一个数，数出他们的最大子序和。
样例输入
6 4
1 -3 5 1 -2 3样例输出
7思路
使用前缀和数组，使用单调队列维护区间最小值，枚举窗口(长度为m)的末尾位置i，遍历得sum[i+1]-sum[q.front()]的最小值，时间复杂度为O(n)。
代码实现
#include<iostream>
#include<deque>
#include<cinttypes>
using namespace std;
#define MAXSIZE 300000
int arr[MAXSIZE+5];
int sum[MAXSIZE+5];
int main()
{
int n,m;
cin>>n>>m;
sum[0]=0;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
sum[i]+=sum[i-1]+arr[i];
}
deque<int>q;
int ans=INT32_MIN;
for(int i=0;i<n;i++)
{
while(!q.empty()&&sum[q.back()]>sum[i])
{
q.pop_back();
}
q.push_back(i);
if(i-m==q.front())q.pop_front();
ans=max(ans,sum[i+1]-sum[q.front()]);
}
cout<<ans;
return 0;
}3.设计自动结算系统
请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：
get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1add(value)：将价格为value的商品加入待结算商品队列的尾部remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1
注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)
示例 1：
输入: ["Checkout","add","add","get_max","remove","get_max"] [[],[4],[7],[],[],[]] 输出: [null,null,null,7,4,7]
示例 2：
输入: ["Checkout","remove","get_max"] [[],[],[]] 输出: [null,-1,-1]
代码实现
class Checkout {
public:
deque<int>dq;
queue<int>q;
Checkout() {}
int get_max() {
if(dq.empty())return -1;
return dq.front();
}
void add(int value) {
q.push(value);
while(!dq.empty()&&dq.back()<value)dq.pop_back();
dq.push_back(value);
return ;
}
int remove() {
if(q.empty())return -1;
int a=q.front();
if(dq.front()==a)dq.pop_front();
return a;
}
};4.绝对值不超过限制的最长连续子数组
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
输入：nums = [8,2,4,7], limit = 4 输出：2 解释：所有子数组如下： [8] 最大绝对差 |8-8| = 0 <= 4. [8,2] 最大绝对差 |8-2| = 6 > 4. [8,2,4] 最大绝对差 |8-2| = 6 > 4. [8,2,4,7] 最大绝对差 |8-2| = 6 > 4. [2] 最大绝对差 |2-2| = 0 <= 4. [2,4] 最大绝对差 |2-4| = 2 <= 4. [2,4,7] 最大绝对差 |2-7| = 5 > 4. [4] 最大绝对差 |4-4| = 0 <= 4. [4,7] 最大绝对差 |4-7| = 3 <= 4. [7] 最大绝对差 |7-7| = 0 <= 4. 因此，满足题意的最长子数组的长度为 2 。
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5 输出：4 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3
思路
变长滑动窗口，使用单调队列去维护区间最大值和最小值，若最大最小值的差小于等于limit，则窗口尾部向后滑一个位置，若最大最小值的差大于limit，则窗口头部向后滑，一直滑到符合要求的位置，在这期间记录窗口的最大长度。
代码实现
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
deque<int>max_q,min_q;
int n=nums.size();
int a=0,b=0;
int ans=0;
for(int i=0;i<n;i++)
{
b=i;
while(!min_q.empty()&&nums[min_q.back()]>nums[i])min_q.pop_back();
min_q.push_back(i);
while(!max_q.empty()&&nums[max_q.back()]<nums[i])max_q.pop_back();
max_q.push_back(i);
if(nums[max_q.front()]-nums[min_q.front()]<=limit)
{
ans=max(ans,b-a+1);
continue;
}
else
{
while(nums[max_q.front()]-nums[min_q.front()]>limit)
{
if(min_q.front()==a)min_q.pop_front();
if(max_q.front()==a)max_q.pop_front();
a++;
}
}
}
return ans;
}
};5.最大矩形面积
题目描述
给定从左到右多个矩形，已知这此矩形的宽度都为 1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，打印出该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。
输入
输入共一行，第一个数表示矩形的个数 N。接下来 N 个数表示矩形的大小。（1≤N≤100000）
输出
输出最大矩形面积。
样例输入
7
2 1 4 5 1 3 3样例输出
8思路
分别枚举每个小矩形的高，使用单调栈维护每个小矩形的左右最近小于他的位置，最后在所有的arr[i]*(r[i]-l[i]-1)的值里面取一个最大的值。
代码实现
#include<iostream>
#include<stack>
using namespace std;
#define MAXSIZE 100000
long long arr[MAXSIZE+5];
long long l[MAXSIZE+5],r[MAXSIZE+5];
int main()
{
int n;
cin>>n;
arr[0]=0;
for(int i=1;i<=n;i++)
cin>>arr[i];
arr[n+1]=0;
stack<int>s;
for(int i=0;i<=n+1;i++)
{
while(!s.empty()&&arr[s.top()]>arr[i])
{
r[s.top()]=i;
s.pop();
}
s.push(i);
}
for(int i=n+1;i>=1;i--)
{
while(!s.empty()&&arr[s.top()]>arr[i])
{
l[s.top()]=i;
s.pop();
}
s.push(i);
}
long long ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,arr[i]*(r[i]-l[i]-1));
cout<<ans;
return 0;
}6.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
思路
使用单调栈去维护最近小于关系，每次遇到高度对栈顶元素矮就加进去，一直到遇到高的为止。遇到高的之后要不断对比它矮的元素进行出栈，同时计算体积。体积的计算为(min(h1,h3)-h2)*(j-i-1)，对每一部分的体积进行累加，最后求得结果。
代码实现
class Solution {
public:
int trap(vector<int>& height) {
stack<int>s;
int n=height.size();
int sum=0;
for(int i=0;i<n;i++)
{
while(!s.empty()&&height[s.top()]<height[i])
{
int a=s.top();
s.pop();
if(!s.empty())
{
int b=s.top();
sum+=(min(height[i],height[b])-height[a])*(i-b-1);
}
else continue;
}
s.push(i);
}
return sum;
}
};7.和至少为K的最短子数组
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
示例 1：
输入：nums = [1], k = 1 输出：1
示例 2：
输入：nums = [1,2], k = 4 输出：-1
示例 3：
输入：nums = [2,-1,2], k = 3 输出：3
思路
使用前缀和数组，利用单调队列维护值递增序列，每次入栈时将将要入栈的值和队尾元素比较，小则删至序列单调，大则在入队前和q.front()的值做差，大于等于k则记录，并继续往后找，否则退出循环，不断对符合条件的区间长度进行记录，最后找到最短值。
代码实现
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
deque<int>q;
int n=nums.size();
int ans=n+1;
vector<long long>sums(n+1);
sums[0]=0;
for(int i=1;i<=n;i++)
sums[i]=sums[i-1]+nums[i-1];
for(int i=0;i<=n;i++)
{
while(!q.empty()&&sums[q.back()]>sums[i])
{
q.pop_back();
}
while(!q.empty()&&sums[i]-sums[q.front()]>=k)
{
ans=min(ans,i-q.front());
q.pop_front();
}
q.push_back(i);
}
if(ans==n+1)return -1;
return ans;
}
};8.双生序列
题目描述
u，v 两个序列趋势相同，当且仅当对于任意 l 和 r，均有 RMQ(u,l,r)=RMQ(v,l,r) (1≤l≤r≤n)，
其中 n 是序列长度，RMQ(u,l,r) 是 u 序列从 l 到 r 中的最小值（有可能有多个最小值）的最大下标。
现有两个序列 A={a1,a2,a3,…,an}，B={b1,b2,b3,…,bn} 两个序列
请求出最大的 p，使得A‘={a1,a2,a3,…,ap} 与B‘={b1,b2,b3,…,bp} 趋势相同。
输入
第一行输入一个整数 n(1≤n≤500000)，代表 A、B 序列长度。
接下来两行，每行 n 个正整数，分别代表两个序列相应位置的值。
序列中数字大小均在 int32 范围内。
输出
输出一个整数，代表满足题意的最大 p 值。
样例输入
5
3 1 5 2 4
5 2 4 3 1样例输出
4思路
在前i-1个位置为趋势相同的前提下，如何保证第i个位置加进去之后继续保持趋势相同？——两个单调队列相同，在此情景下等价于长度相同，否则第i个位置不可取，最终长度为i-1。
代码实现
#include<iostream>
#include<deque>
using namespace std;
#define MAXSIZE 500000
int a[MAXSIZE+5],b[MAXSIZE+5];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
deque<int>qa,qb;
for(int i=1;i<=n;i++)
{
while(!qa.empty()&&a[qa.back()]>a[i])
{
qa.pop_back();
}
while(!qb.empty()&&b[qb.back()]>b[i])
{
qb.pop_back();
}
if(qa.size()!=qb.size())
{
cout<<i-1;
return 0;
}
qa.push_back(i);
qb.push_back(i);
}
cout<<n;
return 0;
}
