当前位置：首页 > article >正文

算法-栈和队列篇04-滑动窗口最大值

article 2025/2/23 17:47:37

滑动窗口最大值

力扣题目链接

题目描述

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