【算法】单调队列单调栈

一、单调队列

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

基本概念

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

代码如下：

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

void output(vector<int>& arr) {
	int n = arr.size(), len = 0;
	for (int i = 0; i < n; i++) len += printf("%3d", i);
	cout << "\n";
	
	for (int i = 0; i < len; i++)printf("-");
	cout << "\n";
	
	for (int i = 0; i < n; i++) len += printf("%3d", arr[i]);
	cout << "\n";
}

int main(){
	int n, k;
	cin >> n >> k;
	vector<int> arr;
	deque<int> q;
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		arr.push_back(a);
	}
	output(arr);
	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] = 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 <iostream>
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 < n; i++) cin >> a[i];

	//找滑动窗口最小值
	int hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		if (i - q[hh] == k) hh++; //队头弹出元素
		while (hh <= tt && a[q[tt]] > a[i]) tt--; //队尾弹出元素
		q[++tt] = i; //压入下标
		if (i - k + 1 >= 0)printf("%d ", a[q[hh]]);
	}
	printf("\n");
	//找滑动窗口最大值
	hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		if (i - q[hh] == k) hh++; //队头弹出元素
		while (hh <= tt && a[q[tt]] < a[i]) tt--; //队尾弹出元素
		q[++tt] = i; //压入下标
		if (i - k + 1 >= 0)printf("%d ", a[q[hh]]);
	}
	return 0;
}

方法2：（双端队列）

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	deque<int> q;
	for (int i = 0; i < n; i++)cin >> arr[i];
	for (int i = 0; i < n; i++) {
		if (i - q.front() == k) q.pop_front();
		while (!q.empty() && arr[q.back()] > arr[i])q.pop_back();
		q.push_back(i);
		if (i - k + 1 >= 0) cout << arr[q.front()] << " ";
	}
	cout << endl;

	q.clear();
	for (int i = 0; i < n; i++) {
		if (i - q.front() == k) q.pop_front();
		while (!q.empty() && arr[q.back()] < arr[i])q.pop_back();
		q.push_back(i);
		if (i - k + 1 >=0) cout << arr[q.front()] << " ";
	}
	return 0;
}

区间最值

135. 最大子序和 - AcWing题库

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

其实现方法与上面类似，但是需要注意：

区间最值问题是在不限制子序列连续性的情况下，找到子序列中的最大值或最小值。
而滑动窗口问题则是在限制子序列必须连续的情况下，找到所有长度为k的子序列中的最大值或最小值。

方法1：（数组实现）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
int q[N];
LL s[N];
int main()
{
	int n, m;
	cin >> n >> m;
	//处理为前缀和序列
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] += s[i - 1];
	}
	LL res = -1e10;
	int hh = 0, tt = 0;
	for (int i = 1; i <= n; i++) {
		if (i - q[hh] > m) hh++;
		res = max(res, s[i] - s[q[hh]]);
		while (hh <= tt && s[q[tt]] >= s[i]) tt--;
		
		q[++tt] = i;
	}
	cout << res << "\n";
	return 0;
}

方法2：（双端队列）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;

int main()
{
	int n, m;
	cin >> n >> m;
	//处理前缀和
	vector<LL> s(n + 1);
	s.push_back(0);
	deque<LL> q;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] += s[i - 1];
	}
	q.push_back(0);
	LL res = -1e6;
	for (int i = 1; i <= n; i++) {
		if (i - q.front() > 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 << res << "\n";
	return 0;
}

二、单调栈

基本概念

单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减），即从队首不弹出元素的单调队列就是单调栈。

作用：用于找最近小于关系（单调递增）和最近大于关系（单调递减）

代码如下：

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

void output(vector<int>& arr) {
	int n = arr.size(), len = 0;
	for (int i = 0; i < n; i++) len += printf("%3d", i);
	cout << "\n";
	
	for (int i = 0; i < len; i++)printf("-");
	cout << "\n";
	
	for (int i = 0; i < n; i++) len += printf("%3d", arr[i]);
	cout << "\n";
}

int main(){
	int n;
	cin >> n;
	vector<int> arr;
	arr.push_back(-1); //假如极小值为-1
	stack<int> s;
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		arr.push_back(a);
	}
	arr.push_back(-1); //假如极小值为-1
	vector<int> l(arr.size() + 1), r(arr.size() + 1);
	output(arr);

	//右侧
	for (int i = 0;  i < arr.size(); i++) {
		while (!s.empty() && arr[s.top()] > 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; i++) {
		printf("arr[%d] = %d, right : arr[%d] = %d, left : arr[%d] = %d\n",
			i, arr[i],
			r[i], arr[r[i]],
			l[i], arr[l[i]]);
	}
	return 0;
}

数组实现单调栈：

830. 单调栈

#include <iostream>
using namespace std;
const int N = 10010;

int stk[N], tt ;
int main()
{
	int n;
	cin >> 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;
}