[LeetCode][239]【学习日记】滑动窗口最大值—

[LeetCode][239]【学习日记】滑动窗口最大值——O(n)单调队列

题目

239. 滑动窗口最大值

难度：困难
相关标签
相关企业
提示

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

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释：滑动窗口的位置
最大值
--------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1
3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3
-1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1 输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

解法选择

这道题如果在滑动窗口中每次都进行排序找到最大值，那么复杂度就很高：对于窗口有 k 个的元素，遍历使用 O(k)；对于长度为 n 的数组 nums，有 n-k+1 个窗口，所以复杂度为 O((n−k+1)k)=O(nk)，肯定超时
容易想到：如果使用 map 统计并自动排序，滑动窗口后，插入和删除的元素都会被自动排序，找到最大值的时间复杂度为常数，但是插入元素的时间复杂度为O(logn)，如果 nums 递增，那么就 n 个元素都要插入，时间复杂度为 O(nlog⁡n)
记录窗口中所有数据的排序并没有必要，因为在窗口中，当右侧元素比左侧的元素大，由于窗口是向右移动的，那么只要右侧元素还在窗口中，窗口中的的最大值就一定不可能是左侧那个元素，所以就可以将左侧那个元素放心地移除，所以根本不用记录左边那个元素——总而言之，只需要记录右侧比左侧大的元素

解法1：单调队列

单调队列原始版本

思考过程：

首先，这道题的本质是：在数组中，有一个滑动窗口从左向右不断滑动，每次滑动窗口时，会删除最左边的元素并增加最右边的元素。
思路：这个滑动过程让我想到了队列，即先进先出（FIFO）的数据结构。每次窗口删除或新增元素时，需要快速判断这些操作对窗口内的最大值是否产生影响。因此，可以设定一个队列，其中维护着一个从最左边元素开始逐渐增大的序列，例如：
- 当窗口内有
```
[14, 2, 27]
```
  时，队列会变为
```
[14, 27]
```
这样做的好处是，队列的尾部必然是窗口内的最大值，并且当删除最左边的元素时，可以迅速判断该元素是否影响到队列中的队尾（即最大值）；增加元素时，只需判断其是否大于队尾即可。

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        queue<int> maxQ;
        vector<int> ans;
        if(heights.empty()) return ans;
        //先构建一个以窗口最左侧元素为队头，单调递增的队列
        for(int i=0; i<limit; ++i){
            if(maxQ.empty() || heights[i]>=maxQ.back()){
                maxQ.push(heights[i]);
            }
        }

        for(int i=limit; i<heights.size(); ++i){
            ans.push_back(maxQ.back());
            //保证队列里面始终有元素的情况下
            if(maxQ.front()==heights[i-limit]){
                maxQ.pop();//pop后队列内可能没有元素或者还有元素
                if(maxQ.empty()){
                    for(int j=i-limit+1; j<=i; ++j){//队列为空时，根据当前窗口重新构建单调递增序列
                        if(maxQ.empty() || heights[j]>=maxQ.back()){
                            maxQ.push(heights[j]);
                        }
                    }
                    continue;//如果重新构建了单调递增队列，则无需增加窗口最右侧的元素到队列中
                }
            }
            if(heights[i]>=maxQ.back()){//如果窗口最右侧元素比队列中最大的元素（队尾元素）还大，则添加到队尾
                maxQ.push(heights[i]);
            }
        }
        ans.push_back(maxQ.back());
        return ans;
    }
};

单调队列改进版本

原始版本的单调队列就可以通过LCR183
对比官方解法的单调队列的特点是，原始版本的单调队列是单调递增的，笔者原来的想法是这样就可以通过队列的结尾快速地访问到最大值，而官方的单调队列是将最大值放在队头的，要想快速的访问到最大值，每次插入新的最大值前都需要对队列中原有的值 pop 出来再插入，看起来比较麻烦
但是原始版本的单调队列如果在滑动过程中遇到队列 pop 后为空，就需要根据当前窗口重新构建一个单调队列，复杂度将大大提高，也就是下面这一段代码：

for(int j=i-limit+1; j<=i; ++j){//队列为空时，根据当前窗口重新构建单调递增序列
                        if(maxQ.empty() || heights[j]>=maxQ.back()){
                            maxQ.push(heights[j]);
                        }
                    }

这导致原始单调队列在239. 滑动窗口最大值这一题会遇到超时的问题
但是原始版本的单调队列无法简单地修改为改进版本的单调队列，因为改进的队列存储的是 nums 的下标，这样的好处是相同大小但是不同位置处的数字因为有着不同的下标所以方便区分，在滑动窗口需要更新队列的时候，单纯以下面这行代码更新队列，会导致窗口中重复的最大值只在队列中记录一次

if(maxQ.front()==heights[i-limit]) maxQ.pop_front();

解释：

窗口：[-7,-8,7,5] 队列：[7,5]
while(!maxQ.empty() && heights[i]>=maxQ.back()) maxQ.pop_back();
maxQ.push_back(heights[i]);
窗口：[-8,7,5,7] 队列：[7]（此时开始出错，队列中应该有两个7）
由于直到第一个 7 移出窗口范围时，窗口内的最大值始终是 7，故队列中一直只有一个 7，在第一个 7 移出去后，有：窗口：[5,7,1,6] 队列：[6]（队列中应该是7，而不是6）

在这里插入图片描述

官方单调队列

官方的队列保持了队列始终非空，且单调递减，如果新添加的元素是最大的，那么队列清空后再将新增元素放入队列中；滑动窗口后，如果要删除的元素在队头，直接出队
换而言之，官方单调队列只维护窗口中最大值右侧的单调递减队列，因为当右侧元素比左侧的元素大，由于窗口是向右移动的，那么只要右侧元素还在窗口中，窗口中的的最大值就一定不可能是左侧那个元素，所以就可以将左侧那个元素放心地移除，所以根本不用记录左边那个元素，所以队列为空的时候无需按照整个窗口重新构建队列！
所以原始的单调队列解法的问题是，其维护的是窗口中最大值左侧的单调递增队列，在
[1,2,3,4,4,4,3,2,1] 窗口大小为3 这种题中，当窗口移动到[3,2,1]就需要遍历整个窗口重新构建队列，当窗口很大就会很耗时

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;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/sliding-window-maximum/solutions/543426/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法2：大顶堆

大顶堆，C++中的优先队列，O(logn)插入元素后，最大值永远在队头O(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;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/sliding-window-maximum/solutions/543426/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。