【算法】单调队列&&单调栈

一、单调队列

   用来维护一段区间内的最大值或最小值，例如滑动窗口、区间最值等问题。

基本概念

单调队列是一种存储数据的队列，其中元素的顺序是单调递增或单调递减的。在算法竞赛中，我们一般使用两个单调队列，一个维护单调递增序列，另一个维护单调递减序列。单调队列是一个双端队列。

代码如下：

#include 
#include 
#include 
#include 
using namespace std;
void output(vector& arr) {
	int n = arr.size(), len = 0;
	for (int i = 0; i  k;
	vector arr;
	deque q;
	for (int i = 0, a; i > a;
		arr.push_back(a);
	}
	output(arr);
	for (int i = 0; i  arr[i])q.pop_back();
		q.push_back(i); //压入下标
		if (i - q.front() == k) q.pop_front(); //弹出队头
		printf("[%d, %d] = arr[%d] = %d \n",
			max(i - k + 1, 0), i,
			q.front(),arr[q.front()]);
	}
}

滑动窗口

154. 滑动窗口 - AcWing题库

滑动窗口是一类问题，需要在一个长度为n的序列中，找到所有长度为k的连续子序列中的最大值或最小值。使用单调队列可以在O(n)的时间复杂度内解决该问题。

具体做法如下：

（1）将前k个元素插入单调队列中，并记录队列的最大值或最小值。

（2）从第k+1个元素开始，每次将一个新的元素插入单调队列中。

（3）插入时，先将队列中所有小于等于该元素的队尾元素出队，保证队列中的元素单调递减。

（4）将该元素插入队尾，并记录队列的最大值或最小值。

（5）将长度为k的子序列的最大值或最小值输出即可。

方法1：（数组实现）

#include 
using namespace std;
const int N = 1e6 + 10;
int q[N], a[N]; //数组q用来存下标
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i > a[i];
	//找滑动窗口最小值
	int hh = 0, tt = -1;
	for (int i = 0; i = 0)printf("%d ", a[q[hh]]);
	}
	printf("\n");
	//找滑动窗口最大值
	hh = 0, tt = -1;
	for (int i = 0; i  
方法2：（双端队列）
 
#include 
#include 
#include 
using namespace std;
int main() {
	int n, k;
	cin >> n >> k;
	vector arr(n);
	deque q;
	for (int i = 0; i > arr[i];
	for (int i = 0; i  arr[i])q.pop_back();
		q.push_back(i);
		if (i - k + 1 >= 0) cout  m;
	//处理为前缀和序列
	for (int i = 1; i > s[i];
		s[i] += s[i - 1];
	}
	LL res = -1e10;
	int hh = 0, tt = 0;
	for (int i = 1; i  m) hh++;
		res = max(res, s[i] - s[q[hh]]);
		while (hh = s[i]) tt--;
		
		q[++tt] = i;
	}
	cout  n >> m;
	//处理前缀和
	vector s(n + 1);
	s.push_back(0);
	deque q;
	for (int i = 1; i > s[i];
		s[i] += s[i - 1];
	}
	q.push_back(0);
	LL res = -1e6;
	for (int i = 1; i  m) q.pop_front();
		res = max(res, s[i] - s[q.front()]);
		while (!q.empty() && s[q.back()] >= s[i]) q.pop_back();
		q.push_back(i);
	}
	cout  arr[i]) {
			r[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	//左侧 (倒着扫描)
	while (!s.empty()) s.pop();
	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;
	while(n--)
	{
	    int x;
	    cin>>x;
	    while(tt&&stk[tt]>=x) tt--;
	    if(tt==0) printf("-1 ");
	    else printf("%d ",stk[tt]);
	    stk[++tt]=x;
	}
	return 0;
}
 
 
三、总结
 
单调队列：擅长维护区间【最大/最小】值，最小值对应单调递增队列
 
单调栈：擅长维护最近【大于/小于】关系，
 
 
 
从左侧先入栈就是维护左侧最近关系
 
 
从右侧先入栈，就是维护右侧最近关系。