【leetcode】239滑动窗口最大值

慕雪的小助手正在绞尽脑汁···

慕雪小助手的总结

LongCat-Flash-Chat

题目

给你一个整数数组 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
2
3

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

思路一

说明

我最初自己想的思路是，用一个队列来维护滑动窗口，并用一个当前最大值来记录滑动窗口内的最大值。每次滑动窗口满了（为k），都将这个最大值写入返回值数组中。

当滑动窗口左侧缩限的时候，判断被出队列的是否为最大值

不是最大值，不用更新当前最大值；
是最大值，从队列剩余数据中选出一个新的当前最大值；

这样就能维护出一个题目需要的数组。代码如下

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int curMax = INT32_MIN; // 当前最大值
        vector<int> retV; //最大值返回数组

        int size = 0;// 当前队列长度
        queue<int> que;
        for(auto&e:nums)
        {
            // 长度已经等于3了，需要出一个数字
            if(size == k)
            {
                int popNum = que.front();
                que.pop();
                size--;
                // 出队列的就是最大值，那需要从队列里面剩下的选出一个最大值
                if(popNum == curMax)
                {
                    int count = size;
                    curMax = que.front(); // 重置为队列开头值，避免无法匹配
                    while(count --)
                    {
                        // 选最大值
                        int temp = que.front();
                        curMax = max(curMax,temp);
                        que.pop();
                        que.push(temp); // 再插回去
                    }
                }
                // 出队列的不是最大值，不用处理
            }

            // 长度小于3，需要入数字
            if(size < k)
            {
                curMax = max(curMax,e);
                que.push(e);
                size++;
            }

            // 每次size等于3的时候都将最大值写入数组
            if(size == k)
            {
                retV.push_back(curMax);
            }
        }
        // 数量不足k个，最大值需要插入数组
        if(nums.size() < k)
        {
            retV.push_back(curMax);
        }
        return retV;
    }
};

这个代码的时间复杂度是O(N*K)，因为最差情况视作每次都需要重新遍历队列，时间复杂度就很高了。但思路应该是没有问题的，通过了大部分测试用例，只不过在大测试用例中超时了，因为此时K很大，如果需要重新遍历对列找出第二个最大值，耗时会很高。

当然，我想出了另外一个优化方案，就是对于这种大k的情况，维护一个队列中第二大的数据，就不需要遍历对列了。但这样很麻烦，且这个思路本身就已经不适合解这道题了，于是没有尝试。

思路二

说明

思路二是代码随想录上面的，使用一个单调递增/递减对列来维护这个最大值。对于本题而言，使用单调递减序列更适合。

这个对列需要实现push/pop/front三个功能，其中front就是当前滑动窗口中的最大值：

push：当当前值小于对列尾部值时，直接插入；大于时，出队列尾部数值，直到当前值小于队列尾部数值，插入；
pop：如果滑动窗口删除的数据和队头数据一致，出队头数据（因为这是一个需要被删除的最大值）；不一致则不做任何操作；
front：获取队头数据；

注意，这个单调对列只是针对本体的需求来写的。本体只是需要滑动窗口中的最大值，对于对列而言并不需要维护滑动窗口中的所有元素，只需要维护几个递减的最大值就行了。

本题也不能用堆来实现，因为堆只能删除堆顶元素，堆顶元素不一定是滑动窗口需要移除的元素。这会导致堆内元素和当前滑动窗口内的元素不对应，会出现问题。

使用C++的deque数据结构就可以实现一个这样的对列。deque是stack/queue默认的底层容器，stack/queue在C++中是容器适配器（因为它们并不是直接实现的，而是借助其他容器实现的）。deque的特性让它支持队头队尾的插入删除操作。

// 单调队列（从大到小）
class MyQueue 
{ 
    deque<int> que; // 使用deque来实现单调队列
public:
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    void pop(int value) 
    {
        // 先判断是否为空再判断是否相等
        if (!que.empty() && value == que.front()) 
        {
            que.pop_front();
        }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) 
    {
        while (!que.empty() && value > que.back()) 
        {
            que.pop_back();
        }
        que.push_back(value);
    }
    
    // 查询当前队列里的最大值，直接返回队列前端就可以了。
    int front() 
    {
        return que.front();
    }
};

代码

有了这个单调递减的对列后，我们现在只需要将vector中的元素按K滑动窗口大小往对列输入就可以了。注意，删除元素的时候要删除当前滑动窗口第一个元素，再加入新元素。

第一次遍历后需要插入一次最大值是因为第二个循环可能不会进去，而且第二个循环中会先移动窗口再插入新的最大值，如果不提前插入第一个最大值，可能会漏掉。

另外，本体限定K不会大于数组的长度，所以第一个循环用K做边界是不会数组越界的。

class Solution {
    // 单调队列（从大到小）
    class MyQueue 
    { 
        deque<int> que; // 使用deque来实现单调队列
    public:
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        void pop(int value) 
        {
            // 先判断是否为空再判断是否相等
            if (!que.empty() && value == que.front()) 
            {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value) 
        {
            while (!que.empty() && value > que.back()) 
            {
                que.pop_back();
            }
            que.push_back(value);
        }
        
        // 查询当前队列里的最大值，直接返回队列前端就可以了。
        int front() 
        {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> retV;
        // 先把数组前k个元素送入对列
        for(int i =0;i<k;i++)
        {
            que.push(nums[i]);
        }
        // 先把第一个最大值插入
        retV.push_back(que.front());
        // 然后开始移动滑动窗口
        for(int i = k;i<nums.size();i++)
        {
            // 当i == k 的时候删除0，符合题目条件，不需要修改其他地方的代码
            que.pop(nums[i - k]); // 删除滑动窗口第一个元素
            que.push(nums[i]); // 插入新元素
            // 插入最大值
            retV.push_back(que.front());
        }
        return retV;
    }
};