滑动窗口最大值——单调队列的实践

刺骨的言语ヽ痛彻心扉 2024-03-31 10:40 73阅读 0赞

#### 一、单调队列的介绍 ####

单调队列，即单调递减或单调递增的队列。而且，队首和队尾都可以进行出队操作，但只有队尾可以进行入队操作。它类似于下面这幅图：

![33cbfda4c8424752a89fb473a300593c.png][]

#### 二、[239. 滑动窗口最大值][239.] ####

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。  
返回 滑动窗口中的最大值 。

![ba42152ad6ef40b2a5e5dbb6f99e6ef3.png][]

#### 三、使用单调队列 ####

暴力方法，遍历一遍的过程中每次从窗口中在找到最大的数值,

对于长度为 n 的数组 nums 而言，窗口的数量为 n−k+1，因此该算法的时间复杂度为 O((n−k+1)k)=O(n \* k)的算法。我们可以想到，对于两个相邻（只差了一个位置）的滑动窗口，它们共用着 k−1 个元素，而只有 1 个元素是变化的。我们可以根据这个特点进行优化。

我们需要一个队列，而这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。那怎么知道最大值呢？

所以这里就要维护一个单调递减的队列，这样队头就是最大值。为了保证队头的值最大，后续入队列的元素都是比它小的，而且是依次单调递减的元素。可是一旦发现某个元素入队时，它居然比队头元素更大，此时队列的单调性就不能维持了，我们就要把原来入队的元素都干掉，只留下这个新来的元素，让单调队列一切重新开始。

这个过程有点封建王朝，人们不断的追求权力，但是不允许自己的后来者超过自己，可是皇位不可能永传，新来者会推翻一切，重新洗牌，循环往复。

代码

class Solution {
    public:
        // 求出滑动窗口的最大值
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
            int n = nums.size();
    
            // 为了可以同时弹出队首和队尾的元素，使用deque
            // 使用一个单调队列，存储所有还没有被移除的下标，即窗口的大小，下标对应的值单调递增
            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()] }; // 存入前面K个元素中的最大值
    
            // 开始移动窗口
            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;
        }
    };

#### 四、使用优先队列 ####

对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
            int n = nums.size();
            // pair第一个元素代表值，第二个元素代表索引
            priority_queue<pair<int, int>> q;  // 最大堆
            for (int i = 0; i < k; ++i) {  // 我们将数组前 k 个元素放入优先队列中
                q.emplace(nums[i], i);
            }
    
            vector<int> ans = {q.top().first};  // 最大值
            for (int i = k; i < n; ++i) {  // 当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中
                q.emplace(make_pair(nums[i], i));
                while (q.top().second <= i - k) {  // 此时堆顶的元素就是堆中所有元素的最大值，但是该值如果不在该窗口中
                    q.pop(); // 移除它
                }
                ans.push_back(q.top().first);
            }
            return ans;
        }
    };

参考：

[代码随想录][Link 1]

[力扣][Link 2]

[33cbfda4c8424752a89fb473a300593c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6151660c179b4cbfa4399a303de3d87e.png
[239.]: https://leetcode.cn/problems/sliding-window-maximum/
[ba42152ad6ef40b2a5e5dbb6f99e6ef3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c390115b9837479299cf1d4ba6786874.png
[Link 1]: https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
[Link 2]: https://leetcode.cn/problems/sliding-window-maximum/submissions/