题目链接

LeetCode

题目描述

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

示例 3：

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

示例 4：

输入： nums = [9,11], k = 2
输出： [11]

示例 5：

输入： nums = [4,-2], k = 2
输出： [4]

提示：

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

    解题思路

    方法一：暴力法（超时）

    首先将前k个中的最大值取出
    移动窗口时判断移除的元素是否为最大元素，如果是则在新的窗口中遍历最大值，不是则之前的最大值还在窗口中，将之前的最大值和当前进入窗口的值进行比较。
  1. class Solution {
  2. public:
  3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  4.         vector<int> res;
  5.         int curMax = INT_MIN;
  6.         int len = nums.size();
  7.         for(int i=0;i<k;i++){
  8.             curMax = max(curMax,nums[i]);
  9.         }
  10.         res.push_back(curMax);
  11.         for(int j=0,i=k;i<len;i++){
  12.             if(curMax==nums[j]){
  13.                 curMax = INT_MIN;
  14.                 for(int x=j+1;x<=i;x++){
  15.                     curMax = max(curMax,nums[x]);
  16.                 }
  17.             }
  18.             curMax = max(curMax,nums[i]);
  19.             res.push_back(curMax);
  20.             j++;
  21.         }
  22.         return res;
  23.     }
  24. };
  • 时间复杂度 O(n-n^2)
  • 空间复杂度 O(1)

    方法二：优先队列

    对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为 index。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int len = nums.size();
        priority_queue<pair<int,int>> pq;
        for(int i=0;i<k;i++){
            pq.emplace(nums[i],i);
        }
        res.push_back(pq.top().first);
        for(int i=k;i<len;i++){
            pq.emplace(nums[i],i);
            // 将窗口外 大于当前窗口最大值的元素弹出
            while(pq.top().second <= i-k){
                pq.pop();
            }
            res.push_back(pq.top().first);
        }
        return res;
    }
};
  • 时间复杂度 O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。
  • 空间复杂度 O(n) 队列的空间

    方法三：单调队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int len = nums.size();
        deque<int> dq;
        for(int i=0;i<k;i++){
            while(!dq.empty()&&nums[dq.back()]<=nums[i]){
                dq.pop_back();
            }
            dq.push_back(i);
        }
        res.push_back(nums[dq.front()]);
        for(int i=k;i<len;i++){
            while(!dq.empty()&&nums[dq.back()]<=nums[i]){
                dq.pop_back();
            }
            dq.push_back(i);
            while(!dq.empty()&&dq.front()<=i-k){
                dq.pop_front();
            }
            res.push_back(nums[dq.front()]);
        }
        return res;
    }
};
  • 时间复杂度 O(n)
  • 空间复杂度 O(k) k为窗口大小