LeetCode 239. 滑动窗口最大值

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 239. 滑动窗口最大值

思路分析

单调队列

参考代码

func maxSlidingWindow(nums []int, k int) []int {
	var res []int
	var deque []int // 存储下标，维护单调递减队列

	for i := 0; i < len(nums); i++ {
		// 移除队尾所有比当前元素小的值
		for len(deque) > 0 && nums[i] >= nums[deque[len(deque)-1]] {
			deque = deque[:len(deque)-1]
		}

		// 将当前下标加入队列
		deque = append(deque, i)

		// 如果队首的下标已经不在窗口中，移除它
		if deque[0] <= i-k {
			deque = deque[1:]
		}

		// 窗口形成后，记录最大值
		if i >= k-1 {
			res = append(res, nums[deque[0]])
		}
	}

	return res
}

时间复杂度：O(n)，每个元素最多进队列一次、出队列一次。

空间复杂度：O(k)，队列最多维护 k 个元素的下标。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/01328393