LeetCode 239. 滑动窗口最大值

Categories:

Tags:

题目描述
思路分析
1. 解法一：单调队列（推荐）
2. 解法二：优先队列（大根堆）
相似题目

题目描述

✅ 239. 滑动窗口最大值

思路分析

解法一：单调队列（推荐）

核心思路：

暴力做法对每个窗口遍历取最大值，时间复杂度 O(nk)。优化目标：用单调双端队列在 O(1) 时间内获取当前窗口最大值。

维护一个严格递减的双端队列（存下标），保证队首始终是当前窗口最大值的下标。

入队规则（右端）：新元素 nums[i] 入队前，从队尾弹出所有值不大于 nums[i] 的元素。原因：若 nums[j] ≤ nums[i] 且 j < i，则 nums[j] 既比 nums[i] 小又会更早离开窗口，永远不可能成为未来窗口的最大值，可以安全丢弃。

出队规则（左端）：若队首下标 ≤ i - k，说明该下标已离开当前窗口，弹出。

取最大值：队首下标对应的元素值即为当前窗口的最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，每个元素最多入队一次、出队一次

空间复杂度：O(k)，其中 k 为窗口大小，队列中最多存 k 个下标

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // 双端队列存储下标，维护单调递减顺序
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 从队尾移除所有值不大于 nums[i] 的下标，保持队列单调递减
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 队首下标已超出窗口范围，移除
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            // 窗口完整后，记录当前窗口最大值
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}

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

    for i := 0; i < len(nums); i++ {
        // 从队尾移除所有值不大于 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 log n)，其中 n 为数组长度，每个元素最多入堆一次，堆操作为 O(log n)

空间复杂度：O(n)，堆中最多存储 n 个元素

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // 大根堆，存储 [值, 下标]，按值降序排列
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < n; i++) {
            maxHeap.offer(new int[]{nums[i], i});
            // 堆顶元素下标已超出窗口左边界，懒删除
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            // 窗口完整后，堆顶即为当前窗口最大值
            if (i >= k - 1) {
                res[i - k + 1] = maxHeap.peek()[0];
            }
        }
        return res;
    }
}

import "container/heap"

// MaxHeap 实现大根堆，存储 [值, 下标]
type MaxHeap [][2]int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i][0] > h[j][0] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maxSlidingWindow(nums []int, k int) []int {
    res := make([]int, 0, len(nums)-k+1)
    h := &MaxHeap{}
    heap.Init(h)

    for i := 0; i < len(nums); i++ {
        heap.Push(h, [2]int{nums[i], i})
        // 懒删除：堆顶下标已超出窗口左边界
        for (*h)[0][1] <= i-k {
            heap.Pop(h)
        }
        // 窗口完整后，堆顶为当前窗口最大值
        if i >= k-1 {
            res = append(res, (*h)[0][0])
        }
    }

    return res
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口
480. 滑动窗口中位数	困难	滑动窗口、堆
862. 和至少为 K 的最短子数组	困难	单调队列
155. 最小栈	简单	辅助结构维护最值
1438. 绝对差不超过限制的最长连续子数组	中等	单调队列
面试题 59 - I. 滑动窗口的最大值	中等	单调队列
2398. 预算内的最多机器人数目	困难	单调队列、滑动窗口

本文作者: HGNULB

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