滑动窗口最大值

力扣题目链接

题目描述

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

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

解题思路

这道题目一开始我是直接使用滑动窗口去做的， 在过程中使用一个pair来记录当前窗口内最大的数及其位置。但是该方法的时间复杂度是O(n)-O(nm)，有一个比较大的测试用例会超时，所以借鉴了一下他人的解法。

滑动窗口解法(超时)

定义一个ans数组用于保存答案，一个pair保存当前窗口的最大值及其位置；
先遍历数组前k个，并记录下最大数nums[i]和i；
然后遍历后面的数据，并遵循以下规则：

• 当下一个数据大于窗口最大数据，直接修改pair；
• 当最大数据在窗口头部即将出去时，重新寻找最大值；
  把最大值存在ans中。

优先队列(正解)

定义一个ans数组和双端队列dq；
直接遍历数组，并遵循以下规则：

• 当下一个数据大于等于当前队列中队尾的数据时，把队尾数据弹出，并继续这个过程直到队列为空或者队尾数据大于下一个数据；
• 把队列头部的数据放入ans中；
• 当头部数据的下标比i小k时，说明该数据已经出了窗口范围，将其从头部弹出；
  返回ans即可。

题解

滑动窗口解法(超时)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        vector<int> mpair = {0, nums[0]};

        for(int i = 1; i < k; i++){
            if(nums[i] > mpair[1]){
                mpair = {i, nums[i]};
            }
        }
        ans.push_back(mpair[1]);

        for(int i = 0; i < nums.size() - k; i++){
            if(nums[i + k] > mpair[1]){
                //窗口尾部加入元素大于原窗口最大元素，直接替换
                mpair = {i + k, nums[i + k]};
            }
            else if(mpair[0] == i){
                //原窗口最大元素在头部，即将出窗口，重新寻找最大值
                mpair = {i + 1, nums[i + 1]};
                for(int j = 2; j <= k; j++){
                    if(nums[i + j] > mpair[1]){
                        mpair = {i + j, nums[i + j]};
                    }
                }
            }
            ans.push_back(mpair[1]);
        }

        return ans;
    }
};

优先队列(正解)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;

        for(int i = 0; i < nums.size(); i++){
            while(!dq.empty() && nums[dq.back()] <= nums[i]){
                dq.pop_back();
            }
            dq.push_back(i);
            if(i - dq.front() >= k){
                dq.pop_front();
            }
            if(i >= k - 1){
                ans.push_back(nums[dq.front()]);
            }
        }

        return ans;
    }
};

总结

这道题目还是很有难度的，因为数据给的非常苛刻；
也是让我见到了双端队列更加灵活的用法，一开始有想到用优先队列，但是在存储数据上，有一个没法判断说明时候数据出窗口，所以没采用；这里通过存储下标i，然后比较大小和读取数据的时候再访问nums数组，这种方法去实现优先队列就比较难以想到。