LeetCode239. [H]滑动窗口最大值(优先队列、双端队列)

239. 滑动窗口最大值 - 力扣（LeetCode）

一、思路

维护一个优先队列/双端队列，队首元素即为窗口中的最大值

二、解题方法

2.1 优先队列

将窗口中的元素插入到优先队列中，队首的元素即为队列中的最大值，唯一需要注意的是：

我们并不需要每一次都把滑出窗口的元素出队，只需要在每次获取最大值的时候，判断队首元素是否处于窗口内即可

index<=i-k代表元素不在窗口内

2.1.1 代码：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        //优先队列
        priority_queue<pair<int,int>> queue;
        vector<int> ans;
        //初始窗口
        for(int i=0;i<k;i++)
        {
            queue.emplace(make_pair(nums[i],i));
        }
        //初始窗口的最大值
        ans.emplace_back(queue.top().first);
        for(int i=k;i<n;i++)
        {
            //滑入新的元素
            queue.emplace(make_pair(nums[i],i));
            //如果当前优先队列队首的元素处于窗口外，直接移除
            while(!queue.empty()&&queue.top().second<=i-k)
            {
                queue.pop();
            }
            //当队首元素不是窗口外元素时，代表是该元素是当前窗口的最大值
            ans.emplace_back(queue.top().first);
        }
        return ans;
    }
};

2.1.2 复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。
空间复杂度：O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间，只计算额外的空间使用。

2.2 双端队列（单调队列）

对于一个新入队的元素（简称为x），一定有已经入队的元素一定比新元素先出队，那么凡是小于新入队元素的旧元素，无论其是否在窗口中，窗口中最大的元素一定不是它

因为如果该旧元素在窗口中，x一定在窗口中，窗口中的最大元素一定>=x
如果他不在窗口中，那完全不需要考虑这个旧元素

既小于新入队元素的旧元素已经不可能是窗口中的最大元素

此外我们还需要注意每当由新元素入队的时候，确保队首的元素在窗口中

2.2.1 代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        if(n==0 || k==0) return {};
        vector<int> res;
        //双端队列
        deque<int> deque;
        //初始化第一个窗口
        for(int i=0;i<k;i++)
        {
            //凡是比新入队元素小的，都已经没用了，因为旧的元素一定比新的元素早出窗口，
            //而新元素大于这些旧的元素，且只要新元素在窗口中，这些旧元素无论是否在窗口，窗口中的最大值一定>=新元素
            //所以这些旧元素可以直接移出队列
            while(!deque.empty()&&nums[i]>deque.back())
            {
                deque.pop_back();
            }
            deque.push_back(nums[i]);
        }
        //插入初始窗口的结构
        res.emplace_back(deque.front());
        

        for(int i=k;i<n;i++)
        {
            //如果队首元素是刚出队的元素，要将其移除
            if(deque.front()==nums[i-k])
            {
                deque.pop_front();
            }
            //同上，移除队尾小于新元素的旧元素
            while(!deque.empty()&&nums[i]>deque.back())
            {
                deque.pop_back();
            }
            deque.push_back(nums[i]);
            //添加结果
            res.emplace_back(deque.front());
        }
        return res;
    }
};

一些解释

//如果队首元素是刚出队的元素，要将其移除
if(deque.front()==nums[i-k])
{
    deque.pop_front();
}

如果新入队的元素恰巧成为队首，是否会移除新元素，导致窗口中的最大值有误？

实则不然如果新入队的元素成为front，代表队列中的元素变为{nums[i],nums[i-k].......}，代表刚刚出队的元素=新入队的元素=queue.front

2.2.2 复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。
空间复杂度：O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1 个元素，因此队列使用的空间为 O(k)。

‍