LeetCode 239: 滑动窗口最大值

解答

代码一：大根堆

最好的解法是单调队列，但是一开始想的是大根堆

问题在于如何将滑动窗口移出的元素从大根堆中删除，大根堆只能pop，没法移除特定的元素。这里就陷入了困境。

解决方法是判断top是否在滑动窗口内，因此要将下标放入大根堆中，判断top->second是否大于i-k

滑动窗口的大小永远小于等于k，但是这里大根堆的大小最坏情况是O(n)，自己没有想到上面的转换，

很大程度上我就是既想删除移出的元素，又想保持大根堆元素小于等于k，陷入了困境。现在是pop堆顶并判断是否在滑动窗口内，而且空间复杂度O(n)

// 作者：LeetCode-Solution
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;}
};

代码二：单调队列

单调队列典型题目，
单调队列维护一个区间内元素单调递增/递减，在元素入队的时候比较像单调栈，在元素移出滑动窗口时可以从另一端pop
里面有一个细节是单调队列中存储的是下标索引，这样可以判断front是否处于滑动窗口之外

deque平时用的少，这里记录一下常用方法

// my solution
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {if(k==1) return nums;vector<int> ans(nums.size()-k+1, -1);deque<int> dq;// [0, k-1)预处理int now = 0, idx=0;for(int i=0; i<k-1; i++){now = nums[i];if(dq.empty()) dq.push_back(i);else if(now < nums[dq.back()]) dq.push_back(i);else{ // now >= dp.back()while(!dq.empty() && now>= nums[dq.back()]){dq.pop_back();}dq.push_back(i);}}for(int i=k-1; i<nums.size(); i++){now = nums[i];// windows scope: [i-k+1,i]if(dq.front() < i-k+1) dq.pop_front();if(dq.empty()) dq.push_back(i);else if(now < nums[dq.back()])  dq.push_back(i);else{ // now >= dp.back()while(!dq.empty() && now>=nums[dq.back()])dq.pop_back();dq.push_back(i);}ans[idx++] = dq.front();}for(int i=0; i<ans.size(); i++)ans[i] = nums[ans[i]];return ans;}
};