LeetCode 剑指 Offer 59 - I. 滑动窗口的最大值

Categories:

题目描述
思路分析
1. 解法一：单调队列（推荐）
相似题目

题目描述

✅ 剑指 Offer 59 - I. 滑动窗口的最大值

思路分析

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

核心思路：

用双端队列维护下标，保证队列内对应值单调递减。

新元素入队前，弹出队尾所有小于等于它的元素。

队首若已滑出窗口，则弹出队首。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(k)，其中 k 表示窗口大小。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }

        int[] res = new int[nums.length - k + 1];
        int idx = 0;
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // 保持队列单调递减
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 移除滑出窗口的下标
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            if (i >= k - 1) {
                res[idx++] = nums[deque.peekFirst()];
            }
        }

        return res;
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 {
        return []int{}
    }

    res := make([]int, 0, len(nums)-k+1)
    deque := make([]int, 0)

    for i := 0; i < len(nums); i++ {
        // 保持队列单调递减
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
            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
}

相似题目

题目	难度	考察点
239. 滑动窗口最大值	困难	单调队列
1438. 绝对差不超过限制的最长连续子数组	中等	单调队列
862. 和至少为 K 的最短子数组	困难	单调队列
480. 滑动窗口中位数	困难	双堆
76. 最小覆盖子串	困难	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/44764303