单调队列与滑动窗口问题总结

2023-11-19 10:52:22

例题

LeetCode 239. Sliding Window Maximum

可能没有办法注册，就点这里

题目

给你一个整数数组 nums，有一个大小为 \(k\) 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 \(k\) 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

简要分析

这道题用暴力显然是过不了的（时间复杂度\(O(nk)\)）。这时候我们就需要……

单调队列（Humdrum Queue）

了解单调队列，需要知道什么是单调。

这里用函数的单调性的定义，与这里的单调也大同小异。

函数的单调性（monotonicity）也可以叫做函数的增减性。当函数 f(x) 的自变量在其定义区间内增大（或减小）时，函数值f(x)也随着增大（或减小），则称该函数为在该区间上具有单调性。

单调队列也是一样，可以看成队列的一个子集，满足\(\forall i(1 \le i \lt SIZE)\text{ } queue[i] \le queue[i+1]\)或\(\forall i(1 \le i \lt SIZE)\text{ } queue[i] \ge queue[i+1]\)。

实现

需要实现这些功能：

struct HumdrumQueue{
	void pop(int val){
		
	}
	void push(int val){
		
	}
	int front(){
		return 0;
	}
	int size(){
		return 0;
	}
};

底层容器

由于单调队列本来就是队列的变种，STL队列又基于deque，所以我就私自选择deque了。

完整代码（我还顺便加了一个back()）:

struct HumdrumQueue {
	deque<int> q;

	void pop(int val) {
		if (!this->q.empty() && this->q.front() == val) {
			this->q.pop_front();
		}
	}
	void push(int val) {
		while (!this->q.empty() && val > this->q.back()) {
			this->q.pop_back();
		}
		this->q.push_back(val);
	}
	int front() {
		return this->q.front();
	}
	int back() {
		return this->q.back();
	}
	int size() {
		return this->q.size();
	}
};

其中，pop函数需要判队首与本数相同。

push则使用大了就出队的思路。请自己思考为什么。

解决滑动窗口问题

vector<int> maxSlidingWindow(vector<int> nums, int k) {
	HumdrumQueue hq;
	vector<int> answer;
	for (int i = 0; i < k; i++) {
		hq.push(nums[i]);
	}
	answer.push_back(hq.front());
	for (int i = k; i < int(nums.size()); i++) {
		hq.pop(nums[i - k]);
		hq.push(nums[i]);
		answer.push_back(hq.front());
	}
	return answer;
}

\(\textbf{移除最前元素，加入最后元素，记录最大值，Well done!!}\)

整合，提交

LeetCode的提交方法有些不同

class Solution {
	public:
		vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	
			struct HumdrumQueue {
				deque<int> q;

				void pop(int val) {
					if (!this->q.empty() && this->q.front() == val) {
						this->q.pop_front();
					}
				}
				void push(int val) {
					while (!this->q.empty() && val > this->q.back()) {
						this->q.pop_back();
					}
					this->q.push_back(val);
				}
				int front() {
					return this->q.front();
				}
				int back() {
					return this->q.back();
				}
				int size() {
					return this->q.size();
				}
			};


			HumdrumQueue hq;
			vector<int> answer;
			for (int i = 0; i < k; i++) {
				hq.push(nums[i]);
			}
			answer.push_back(hq.front());
			for (int i = k; i < int(nums.size()); i++) {
				hq.pop(nums[i - k]);
				hq.push(nums[i]);
				answer.push_back(hq.front());
			}
			return answer;

		}
};

时间复杂度与空间复杂度为\(O(n)\)，完美解决。

其他题目

P1886 滑动窗口 /【模板】单调队列

题目

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is \([1,3,-1,-3,5,3,6,7]\), and \(k = 3\)。

分析

这道题跟原来的题差不多。
只是添加了一个最小的。

#include <bits/stdc++.h>
using namespace std;

struct HumdrumQueue {
	deque<int> q;

	void pop(int val) {
		if (!this->q.empty() && this->q.front() == val) {
			this->q.pop_front();
		}
	}
	void push(int val) {
		while (!this->q.empty() && val > this->q.back()) {
			this->q.pop_back();
		}
		this->q.push_back(val);
	}
	void push2(int val) {
		while (!this->q.empty() && val < this->q.back()) {
			this->q.pop_back();
		}
		this->q.push_back(val);
	}
	int front() {
		return this->q.front();
	}
	int back() {
		return this->q.back();
	}
	int size() {
		return this->q.size();
	}
};

vector<int> maxSlidingWindow(vector<int> nums, int k) {
	HumdrumQueue hq;
	vector<int> answer;
	for (int i = 0; i < k; i++) {
		hq.push(nums[i]);
	}
	answer.push_back(hq.front());
	for (int i = k; i < int(nums.size()); i++) {
		hq.pop(nums[i - k]);
		hq.push(nums[i]);
		answer.push_back(hq.front());
	}
	return answer;
}

vector<int> minSlidingWindow(vector<int> nums, int k) {
	HumdrumQueue hq;
	vector<int> answer;
	for (int i = 0; i < k; i++) {
		hq.push2(nums[i]);
	}
	answer.push_back(hq.front());
	for (int i = k; i < int(nums.size()); i++) {
		hq.pop(nums[i - k]);
		hq.push2(nums[i]);
		answer.push_back(hq.front());
	}
	return answer;
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	vector<int> result = maxSlidingWindow(v, k);
	vector<int> result2 = minSlidingWindow(v, k);
	for (int i = 0; i < result2.size(); i++) {
		cout << result2[i] << ' ';
	}
	cout << '\n';
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << ' ';
	}
	return 0;
}

其他推荐题目

UVA11572 唯一的雪花 Unique Snowflakes

我用的是另一个做法：

#include <bits/stdc++.h>
using namespace std;

int a[1000005];

int main(){
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);	
		}
		set<int> s;
		int left=0,right=0,answer=0;
		while(right<n){
			while(right<n&&!s.count(a[right])){
				s.insert(a[right++]);
			}
			answer = max(answer,right-left);
			s.erase(a[left++]);
		}
		printf("%d\n",answer);
	}
	return 0;
}

滑动窗口/单调队列模板代码

struct HumdrumQueue {
	deque<int> q;

	void pop(int val) {
		if (!this->q.empty() && this->q.front() == val) {
			this->q.pop_front();
		}
	}
	void push(int val) {
		while (!this->q.empty() && val > this->q.back()) {
			this->q.pop_back();
		}
		this->q.push_back(val);
	}
	void push2(int val) {
		while (!this->q.empty() && val < this->q.back()) {
			this->q.pop_back();
		}
		this->q.push_back(val);
	}
	int front() {
		return this->q.front();
	}
	int back() {
		return this->q.back();
	}
	int size() {
		return this->q.size();
	}
};

vector<int> maxSlidingWindow(vector<int> nums, int k) {
	HumdrumQueue hq;
	vector<int> answer;
	for (int i = 0; i < k; i++) {
		hq.push(nums[i]);
	}
	answer.push_back(hq.front());
	for (int i = k; i < int(nums.size()); i++) {
		hq.pop(nums[i - k]);
		hq.push(nums[i]);
		answer.push_back(hq.front());
	}
	return answer;
}

vector<int> minSlidingWindow(vector<int> nums, int k) {
	HumdrumQueue hq;
	vector<int> answer;
	for (int i = 0; i < k; i++) {
		hq.push2(nums[i]);
	}
	answer.push_back(hq.front());
	for (int i = k; i < int(nums.size()); i++) {
		hq.pop(nums[i - k]);
		hq.push2(nums[i]);
		answer.push_back(hq.front());
	}
	return answer;
}

其中HumdrumQueue.push是大的，HumdrumQueue.push2是小的。

码农公寓

例题

题目