跳转至

239 滑动窗口的最大值

单调队列

有时间的话阅读一下这篇文章

https://labuladong.online/algo/data-structure/monotonic-queue/#%E4%B8%80%E3%80%81%E6%90%AD%E5%BB%BA%E8%A7%A3%E9%A2%98%E6%A1%86%E6%9E%B6

以下文字来源于以上文章,这解释了为什么使用单调队列:

给你一个数组 window,已知其最值为 A,如果给 window 中添加一个数 B,那么比较一下 A 和 B 就可以立即算出新的最值;但如果要从 window 数组中减少一个数,就不能直接得到最值了,因为如果减少的这个数恰好是 A,就需要遍历 window 中的所有元素重新寻找新的最值。

这个场景很常见,但不用单调队列似乎也可以,比如优先级队列也是一种特殊的队列,专门用来动态寻找最值的,我创建一个大(小)顶堆,不就可以很快拿到最大(小)值了吗?

如果单纯地维护最值的话,优先级队列很专业,队头元素就是最值。但优先级队列无法满足标准队列结构「先进先出」的时间顺序,因为优先级队列底层利用二叉堆对元素进行动态排序,元素的出队顺序是元素的大小顺序,和入队的先后顺序完全没有关系。

所以,现在需要一种新的队列结构,既能够维护队列元素「先进先出」的时间顺序,又能够正确维护队列中所有元素的最值,这就是「单调队列」结构。

「单调队列」这个数据结构主要用来辅助解决滑动窗口相关的问题,前文 滑动窗口核心框架 把滑动窗口算法作为双指针技巧的一部分进行了讲解,但有些稍微复杂的滑动窗口问题不能只靠两个指针来解决,需要上更先进的数据结构。

比方说,你注意看前文 滑动窗口核心框架 讲的几道题目,每当窗口扩大(right++)和窗口缩小(left++)时,你单凭移出和移入窗口的元素即可决定是否更新答案。

但本文开头说的那个判断一个窗口中最值的例子,你无法单凭移出窗口的那个元素更新窗口的最值,除非重新遍历所有元素,但这样的话时间复杂度就上来了,这是我们不希望看到的。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> window;
        int n = nums.size();
        vector<int> res;
        for(int i = 0; i < n; i++){
            // 移动滑动窗口头部 
            // 当前滑动窗口头部idx 如果比理想的头部i - k + 1要小,则调整滑动窗口头部
            while(!window.empty() && window.front() < i - k + 1){
                window.pop_front();
            }
            // 移动滑动窗口尾部
            while(!window.empty() && nums[i] > nums[window.back()]){
                window.pop_back();
            }
            window.push_back(i);
            // 更新滑动窗口最大值
            // 当i >= k -1 说明滑动窗口已填满,可以开始移动和获取最大值
            if(i >= k - 1)
                res.push_back(nums[window.front()]);
        }
        return res;
    }
};

时间复杂度:O(n),其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次,并且最多被弹出队列一次,因此时间复杂度为 O(n)。

空间复杂度:O(k)。与方法一不同的是,在方法二中我们使用的数据结构是双向的,因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1 个元素,因此队列使用的空间为 O(k)