题目链接

题目描述

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

提示

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

  • 1 <= k <= nums.length

    思路

    思路1：大根堆（优先队列）

    要求最大值，我们可以考虑使用大根堆。
    初始时，将 k 个元素放入堆中，然后移动窗口，将新元素放入堆中，但此时堆顶元素可能已经不在窗口中了，因此我们需要判断堆顶元素是否在窗口中。
    解决方法是，堆元素为一个二元数组 pair<int, int> (num, index) ，每次判断堆顶元素即可。

    思路2：单调队列

    类似于单调栈，我们设想一个单调队列 MonotoneQueue ，这个队列里的元素是单调的（本题为单调减）。它有如下基本操作：

  • void pop(num) 如果队首元素等于 num ，则弹出队首元素，否则不进行任何操作。

  • void push(num) 如 num 大于队尾元素，那么弹出队尾元素继续比较，直到 num 不大于队尾元素，此操作保证了单调性。
  • int getMax() 取队首元素，即最大值。

我们使用上述的单调队列解决本题：在窗口移动的过程中，加入新的元素，并判断被移出窗口的元素是否要从队列中移除，取最大值就是此时窗口的最大值。

思路3：分治+DP

将数组 nums 按 k 个一组分组，最后一组可能不足 k 个。那么窗口 num[i] 到 num[i + k - 1] 中最大值有两种情况：

  • i 是 k 的倍数，那么窗口 num[i] 到 num[i + k - 1] 恰好为一个分组。
  • i 不是 k 的倍数，设 j 为 k 的倍数，且 i < j <= i + k - 1 ，窗口 num[i] 到 num[i + k - 1] 会跨越 num[i] 到 num[j - 1] 和 num[j] 到 num[i + k - 1] 两个分组，因此我们要求前者的后缀和后者的前缀的最大值。

我们使用DP来解决前后缀的值。

题解

思路1：大根堆（优先队列）

  1. class Solution {
  2.    public:
  3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  4.         priority_queue<pair<int, int>> maxHeap;
  5.         for (int i = 0; i < k; ++i) {
  6.             maxHeap.emplace(nums[i], i);
  7.         }
  8.         vector<int> ans = {maxHeap.top().first};
  9.         for (int i = k; i < (int)nums.size(); ++i) {
  10.             maxHeap.emplace(nums[i], i);
  11.             while (maxHeap.top().second <= i - k) {
  12.                 maxHeap.pop();
  13.             }
  14.             ans.emplace_back(maxHeap.top().first);
  15.         }
  17.         return ans;
  18.     }
  19. };

思路2：单调队列

  1. class MonotoneQueue {
  2.    private:
  3.     deque<int> _queue;
  5.    public:
  6.     MonotoneQueue(){};
  7.     ~MonotoneQueue(){};
  8.     void pop(int value) {
  9.         if (!_queue.empty() && _queue.front() == value) {
  10.             _queue.pop_front();
  11.         }
  12.     }
  14.     void push(int value) {
  15.         while (!_queue.empty() && _queue.back() < value) {
  16.             _queue.pop_back();
  17.         }
  18.         _queue.push_back(value);
  19.     }
  21.     int getMax() {
  22.         return _queue.front();
  23.     }
  24. };
  26. class Solution {
  27.    public:
  28.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  29.         MonotoneQueue monotoneQueue;
  30.         for (int i = 0; i < k; ++i) {
  31.             monotoneQueue.push(nums[i]);
  32.         }
  33.         vector<int> ans = {monotoneQueue.getMax()};
  34.         for (int i = k; i < (int)nums.size(); ++i) {
  35.             monotoneQueue.pop(nums[i - k]);
  36.             monotoneQueue.push(nums[i]);
  37.             ans.emplace_back(monotoneQueue.getMax());
  38.         }
  40.         return ans;
  41.     }
  42. };

思路3：分治+DP

  1. class Solution {
  2.    public:
  3.     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  4.         int n = nums.size();
  5.         vector<int> prefixMax(n), suffixMax(n);
  6.         vector<int> ans;
  7.         prefixMax[0] = nums[0];
  8.         for (int i = 1; i < n; ++i) {
  9.             prefixMax[i] = 0 == i % k ? nums[i] : max(prefixMax[i - 1], nums[i]);
  10.         }
  11.         suffixMax[n - 1] = nums[n - 1];
  12.         for (int i = n - 2; i >= 0; --i) {
  13.             suffixMax[i] = 0 == (i + 1) % k ? nums[i] : max(suffixMax[i + 1], nums[i]);
  14.         }
  16.         for (int i = 0; i <= n - k; ++i) {
  17.             ans.emplace_back(max(prefixMax[i + k - 1], suffixMax[i]));
  18.         }
  20.         return ans;
  21.     }
  22. };

复杂度分析

思路1：大根堆（优先队列）

  • 时间复杂度：0239-滑动窗口最大值 - 图1

  • 空间复杂度：0239-滑动窗口最大值 - 图2

    思路2：单调队列

  • 时间复杂度：0239-滑动窗口最大值 - 图3

  • 空间复杂度：0239-滑动窗口最大值 - 图4

    思路3：分治+DP

  • 时间复杂度：0239-滑动窗口最大值 - 图5

  • 空间复杂度：0239-滑动窗口最大值 - 图6