【算法日记】力扣239 滑动窗口最大值

发布于:2024-10-18 ⋅ 阅读:(30) ⋅ 点赞:(0)

题目描述

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

思路

首先,最好想的是暴力解决,但是暴力方法的时间复杂度是O(n * k),当n或者k增加,乘积将会非常大,非常容易TLE。不妨换一种方法,我们使用一个队列,这个队列比较特殊,在队首的是这个区间内的最大值,有了这个队列,这个题就会非常好解决,但是STL中没有这样的队列,我们只能手搓一下这个队列。手搓之前,我们先来构思一下:

  1. 这个类需要有队列的基本功能
  2. pop出来的时候,只有当参数等于队列前元素时弹出队列前元素
  3. push进去的时候,当参数大于队尾时,pop队尾所有元素,该元素push队列(保证队尾元素是即将最大的元素)
  4. front函数就很简单了,调用就告诉你这个区间的最大值

基于上面的美好愿景,我们使用deque来实现,也就是我们的这个队列是基于deque魔改

deque<int> que;

deque是一个双向队列

下面是这个类的源码:

class MyQueue {
    public:
    deque<int> que;

    // 函数说明:当参数等于队列前元素时弹出队列前元素
    void pop(int value) {
        if (!que.empty() && value == que.front()) {
            que.pop_front();
        }
    }
    // 函数说明:当参数大于队尾时,pop队尾所有元素,该元素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> res;
        // 先放入前k个元素
        for (int i = 0; i < k; i++) {
            que.push(nums[i]);
        }
        res.push_back(que.front());
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }
};

口头来描述一下主函数的过程,我们说我们现在实现的函数是调用front函数就会告诉你窗口最大值那么怎么判断这个队首元素该弹出了呢,我们可以来滑动窗口,当窗口末尾的元素和这个队列的首项相同时弹出,那么队列的队首就会变为下一个元素,我们称这个元素是即将要变为最大的元素,那么这个元素怎么来的呢?也是通过滑动窗口时,进来的元素和队尾打擂台,比他大,队尾就走,赢家就进入,通过这样,我们就可以保持队尾的元素,也就是即将变大的元素总是最大的,名副其实

程序源码

class Solution {
private:
    class MyQueue {
    public:
        deque<int> que;

        // 函数说明:当参数等于队列前元素时弹出队列前元素
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 函数说明:当参数大于队尾时,pop队尾所有元素,该元素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> res;
        // 先放入前k个元素
        for (int i = 0; i < k; i++) {
            que.push(nums[i]);
        }
        res.push_back(que.front());
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }
};