滑动窗口最大值

题目描述

题目分析

维护一个定长窗口的最大值，每当窗口滑动时都有一个新的元素进入和一个原有的元素离开。
比较简单的方法就是用一个优先队列维护窗口最大值
但是堆的计算成本时最坏时是$O(n\log n)$

优化：

单调队列
相比于堆，堆保留了全部元素，导致维护的成本较高，而单调队列是在保持顺序的情况下只保留符合单调性的元素，不需要重新重新调整结构，换句话说计算的复杂度最坏时为$O(n)$
分块预处理
将所有元素按滑动窗口的大小分块，我们可以得到$[n/k]+1$个块
为了方便的得到块内最大值，我们可以参考前缀和的方式计算块内的前缀最大值，取$i$ 为$k$的倍数时就可以取得第$i/k$块的最大值
问题在于，滑动窗口不一定就是我们分好的块
所以考虑特殊情况，滑动窗口为$[i,j]$，设$m\in [i,j]且k\mid m$(整除)
则$premax[j]$表示了$max(nums[m:j])$
现在问题转为了怎么求$max(nums[i:m))$
我们希望用$i$表示这一段的最大值。注意到$i:m$是一种后缀形式，相应的我们可考虑块内的后缀最大值
定义$sufmax[i]表示了max(nums[i:m))$

解决问题

1.优先队列

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();priority_queue<pair<int, int>> q;for (int i = 0; i < k; ++i) {q.emplace(nums[i], i);}vector<int> ans = {q.top().first};for (int i = k; i < n; ++i) {q.emplace(nums[i], i);while (q.top().second <= i - k) {q.pop();}ans.push_back(q.top().first);}return ans;}
};

2.单调队列

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

3.分块预处理

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();vector<int> prefixMax(n), suffixMax(n);for (int i = 0; i < n; ++i) {if (i % k == 0) {prefixMax[i] = nums[i];}else {prefixMax[i] = max(prefixMax[i - 1], nums[i]);}}for (int i = n - 1; i >= 0; --i) {if (i == n - 1 || (i + 1) % k == 0) {suffixMax[i] = nums[i];}else {suffixMax[i] = max(suffixMax[i + 1], nums[i]);}}vector<int> ans;for (int i = 0; i <= n - k; ++i) {ans.push_back(max(suffixMax[i], prefixMax[i + k - 1]));}return ans;}
};

总结

优先队列，单调队列，动态维护最值
分块预处理，空间换时间，从整体出发，问题分治，对称性思想