单调队列

一个队列, 但是单调. ( 我是懂废话的

窗口内最大值

我们假设要求解一个序列中, 长度为 K 的窗口内扫一遍后每一个窗口内的最值.

看到这种滑动窗口, 可能第一反应是双指针之类的. 不过双指针难以存储当前区间内的最值, 所以比较棘手. 那么借此引入单调队列 ——

那么核心还是说想要借助”历史信息“进行辅助判断 —— 我们既然已经看了之前窗口的信息, 那么能否复用一下, 用于当前窗口最值的判断呢?

我们逐个扫描元素, 每次往队列里面插入新元素的时候考虑一件事情 —— 这个元素的插入, 会让谁失去了价值?

比如说我们的队列已经有了 [7, 5, 3], 然后我们现在要插入 6, 那么显然的, 在当前时间戳及之后, 元素 3 的生命周期(在窗口内的存活时间) 一定比现在插入的 6 要短, 而且 3 比 6 小 —— 那么可以说明, 只有 6 还在队列内, 同时也在窗口内, 那么 3 一定不可能是那个窗口内的最大值. 所以我们可以直接把 3 给 pop 掉. 同理 5 也可以去世 (

那么在 6 插入之前的时间戳, 由窗口之前的插入操作来进行维护, 有点数学归纳法的味道 —— 如果队列中只有一个元素, 那么肯定成立, 我们又保证了每次遇到新元素的时候是成立的, 那么对于任意时刻它都是成立的.

此时有一个小 Trick (其实是上文忽略掉的一点) —— 我们还需要保证“窗口”的长度是 K —— 也就是上面的插入元素的操作再叠上一个正确的窗口长度维护就是完备的了.

那么 Trick 就是我们通常不会在单调队列中存储对应数值, 而是存储其下标 —— 一方面 index 可以表示时间戳 (插入时间). 另一方面, 我们依旧可以方便的通过 index 来访问其存储的数据, 因为序列还在原地没有被修改.

小模板

来一份小模板, 对应 LeetCode 239. 滑动窗口最大值 ——

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
	int n = nums.size();
	std::deque<int> q;
	std::vector<int> ans;
	ans.reserve(n - k + 1);
	
	for (int i = 0; i < n; i++)
	{
		while ((!q.empty()) && nums[q.back()] <= nums[i])
			q.pop_back();
			
		q.push_back(i);
		
		while ((!q.empty()) && q.front() < i - k + 1)
			q.pop_front();
		
		if (i + 1 >= k)
			ans.push_back(nums[q.front()]);
	}
	
	return ans;
}

复杂度分析

上述问题当中, 由于每一个元素都是入队一次出队一次, 所以均摊分析下来时间复杂度是 O(N), 然后由于我们一个队列里最多同时容纳 K 个元素(超过窗口大小存储的元素就应当被判作失效元素而弹出), 所以额外空间复杂度是 O(K)

实际运用

上文提到了——区间最值, 也就是说我们需要维护一个动态区间最值的时候可以考虑使用单调队列来进行实现(当然也要考虑左右边界是不是基本单向移动, 然后旧元素是不是按照时间顺序过期之类的事情) —— 比如什么优化dp, 滑动窗口打什么 Patch 之类的……

能干求区间最值这活的, 什么线段树, ST 表之类的也能干, 所以看实际情况来选择吧.