239. 滑动窗口最大值

🔴   🔖  队列 数组 滑动窗口 单调队列 堆（优先队列）  🔗 LeetCode

题目

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），将其移除。
• 在队列尾部，移除所有小于当前元素的值，因为它们不可能成为当前或之后窗口的最大值。
• 将当前元素的索引加入队列。

2. 获取最大值：对于每一个窗口，队列的前端始终保存当前窗口的最大值的索引。

注意：

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

复杂度分析

• 时间复杂度：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;
};

堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
	let maxHeap = new MaxHeap(),
		res = [];
	for (let i = 0; i < k; i++) {
		maxHeap.insert(nums[i]);
	}
	res.push(maxHeap.heap[0]);
	for (let i = 0; i < nums.length - k; i++) {
		maxHeap.remove(nums[i]);
		maxHeap.insert(nums[i + k]);
		res.push(maxHeap.heap[0]);
	}
	return res;
};

class MaxHeap {
	constructor() {
		this.heap = [];
	}
	insert(value) {
		this.heap.push(value);
		this.heapifyUp(this.heap.length - 1);
		this.heapifyDown(0);
	}
	remove(value) {
		const index = this.heap.indexOf(value);
		if (index !== this.heap.length - 1) {
			this.heap[index] = this.heap.pop();
			this.heapifyDown(index);
		} else {
			this.heap.pop();
		}
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[parent] < this.heap[i]) {
				[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
				i = parent;
			} else {
				break;
			}
		}
	}
	heapifyDown(i) {
		let left = i * 2 + 1,
			right = i * 2 + 2,
			min = i;
		if (this.heap[min] < this.heap[left]) {
			min = left;
		}
		if (this.heap[min] < this.heap[right]) {
			min = right;
		}
		if (min !== i) {
			[this.heap[min], this.heap[i]] = [this.heap[i], this.heap[min]];
			this.heapifyDown(min);
		}
	}
}

相关题目

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