跳到主要内容

239. 滑动窗口最大值

题目描述​

给你一个整数数组 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 73
1 [3 -1 -3] 5 3 6 73
1 3 [-1 -3 5] 3 6 75
1 3 -1 [-3 5 3] 6 75
1 3 -1 -3 [5 3 6] 76
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

出处：LeetCode

解法一：双端队列​

思路​

我们可以使用双端队列来解决这个问题。我们可以维护一个双端队列 deque，用来存储数组 nums 中的索引。在每一步中，我们将 deque 中的元素按照从大到小的顺序存储数组 nums 中的索引，同时我们需要保证 deque 中的元素的索引在滑动窗口的范围内。

在每一步中，我们需要判断 deque 中的第一个元素是否在滑动窗口的范围内，如果不在滑动窗口的范围内，我们需要将其从 deque 中移除。接着，我们需要判断 deque 中的最后一个元素是否小于当前元素 nums[i]，如果小于当前元素 nums[i]，我们需要将其从 deque 中移除，直到 deque 中的最后一个元素大于等于当前元素 nums[i]。

接着，我们需要将当前元素 nums[i] 的索引存储到 deque 中。如果当前元素 nums[i] 的索引大于等于 k - 1，我们需要将 deque 中的第一个元素存储到结果数组中。

代码​

function maxSlidingWindow(nums: number[], k: number): number[] {
  const deque: number[] = [];
  const result: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    if (deque.length && deque[0] < i - k + 1) {
      deque.shift();
    }

    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    deque.push(i);

    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(k)O(k)

解法二：动态规划​

思路​

我们可以使用动态规划来解决这个问题。我们可以将数组 nums 分成大小为 k 的块，然后我们可以计算每个块的最大值。接着，我们可以计算每个块的最大值的最大值。

我们可以使用两个数组 left 和 right 来存储每个块的最大值。其中，left 数组用来存储每个块的左边界的最大值，right 数组用来存储每个块的右边界的最大值。

代码​

function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  const left: number[] = new Array(n);
  const right: number[] = new Array(n);
  const result: number[] = [];

  left[0] = nums[0];
  right[n - 1] = nums[n - 1];

  for (let i = 1; i < n; i++) {
    left[i] = i % k === 0 ? nums[i] : Math.max(left[i - 1], nums[i]);
  }

  for (let i = n - 2; i >= 0; i--) {
    right[i] = i % k === 0 ? nums[i] : Math.max(right[i + 1], nums[i]);
  }

  for (let i = 0; i < n - k + 1; i++) {
    result.push(Math.max(right[i], left[i + k - 1]));
  }

  return result;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)