跳至主要內容

239. 滑动窗口最大值


239. 滑动窗口最大值open in new window

🔴   🔖  队列 数组 滑动窗口 单调队列 堆(优先队列)  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

Output: [3,3,5,5,6,7]

Explanation:

Window position                Max
---------------               -----
[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

Example 2:

Input: nums = [1], k = 1

Output: [1]

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

题目大意

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

返回 滑动窗口中的最大值

解题思路

思路一:双端队列

双端队列(Deque,全称 Double Ended Queue)是一种可以在两端进行插入和删除操作的数据结构。相比于普通的队列(只能在一端插入,在另一端删除),双端队列更加灵活,适用于一些特殊的场景。在 JavaScript 中,双端队列可以使用数组来模拟。

  1. 遍历数组:每次移动滑动窗口时,对双端队列进行更新:
  • 如果队列头部的元素已经不在当前窗口中(即索引小于 i - k + 1),将其移除。
  • 在队列尾部,移除所有小于当前元素的值,因为它们不可能成为当前或之后窗口的最大值。
  • 将当前元素的索引加入队列。
  1. 获取最大值:对于每一个窗口,队列的前端始终保存当前窗口的最大值的索引。

注意:

  • 存储数组元素的索引:不会直接存储数组的值,而是存储元素的索引,以便通过索引访问具体的值,并通过索引判断某个元素是否还在当前滑动窗口中。
  • 保持队列中的元素单调递减:为了保证队列的前端始终是窗口的最大值,会从队列的后端移除所有小于当前元素的索引。

复杂度分析

  • 时间复杂度O(n),其中 n 是数组的长度。每个元素被加入和移除队列至多各一次,因此总的操作次数为 O(n)
  • 空间复杂度O(k),队列的大小在最坏情况下为 k

思路二:堆

大顶堆性质:堆是一棵二叉树,每个节点都满足:父节点的值大于左右子节点的值,堆顶元素是当前堆中的最大值。

使用大顶堆来保存滑动窗口中的 k 个数,每次窗口移动时,移除堆中不在当前窗口的元素,并将新元素入堆,堆顶元素就是滑动窗口中的最大值。

复杂度分析

  • 时间复杂度O(n × (k + log k)),这在最坏情况下比使用双端队列的 O(n) 时间复杂度要高,尤其当 k 接近 n 时,复杂度变为 O(n × k)

    • 插入操作需要 O(log k)
    • 删除操作的复杂度为 O(k),因为需要遍历堆查找需要移除的元素,然后再执行 O(log k) 的调整操作。
    • 对于数组中的每个元素,滑动窗口移动时,我们需要进行一次 插入 和一次 删除 操作,数组长度为 n,因此,最坏情况下总时间复杂度为 O(n * (k + log k))
  • 空间复杂度O(k),堆中的最大元素个数为 k

代码

双端队列
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
	let deque = [],
		res = [];
	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) {
			res.push(nums[deque[0]]);
		}
	}
	return res;
};

相关题目

题号标题题解标签难度
76最小覆盖子串open in new window[✓]哈希表 字符串 滑动窗口
155最小栈open in new window[✓] 设计
159至多包含两个不同字符的最长子串 🔒open in new window哈希表 字符串 滑动窗口
265粉刷房子 II 🔒open in new window数组 动态规划
1696跳跃游戏 VIopen in new window队列 数组 动态规划 2+
2398预算内的最多机器人数目open in new window队列 数组 二分查找 4+
2517礼盒的最大甜蜜度open in new window贪心 数组 二分查找 1+
2530执行 K 次操作后的最大分数open in new window[✓]贪心 数组 堆(优先队列)