滑动窗口最大值（LeetCode 239）

恋喵大鲤鱼

发布于 2023-12-18 13:35:59

1440

发布于 2023-12-18 13:35:59

文章被收录于专栏：C/C++基础

文章目录

1.问题描述
2.难度等级
3.热门指数
4.解题思路
- 方法一：暴力法
- 方法二：优先队列
- 方法三：单调队列
参考文献

1.问题描述

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

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

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

2.难度等级

Hard。

3.热门指数

★★★★☆

出题公司：阿里、腾讯、字节。

4.解题思路

方法一：暴力法

遍历所有的滑动窗口，通过遍历窗口内的所有值获取窗口最大值。

那一共有多少个滑动窗口呢，小学题目，一共可以得到 n-k+1 个滑动窗口。其中 n 为数组长度，k 为滑动窗口大小。

假设 nums = [1,3,-1,-3,5,3,6,7] 和 k = 3，那么窗口数为 n-k+1 = 6。

时间复杂度： O((n-k+1)k)。

空间复杂度：O(1)。不算结果集占用的内存，使用一个变量表示滑动窗口的最大值，所以空间复杂度为 O(1)。

注意： 该解法在 LeetCode 会「超出时间限制」。

下面以 Golang 为例给出实现。

func maxSlidingWindow(nums []int, k int) []int {
    var r []int
    for i := k; i <= len(nums); i++ {
        max := slices.Max(nums[i-k:i])
        r = append(r, max)
    }
    return r
}

方法二：优先队列

好一些的做法，使用优先队列（堆）来做。

在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。注意堆的左右孩子没有大小的顺序。

我们可以构建维护一个大顶堆，堆顶元素就是滑动窗口中的最大值。每一次窗口滑动的时候，我们都需要将新进入窗口的元素加到堆中。

注意： 因为堆不支持删除指定的元素，删除元素只能将堆顶的元素弹出，所以在移动窗口时，左边离开窗口的元素不着急从堆中删除，而是当堆顶元素不在窗口中时，不断地移除堆顶的元素，直到堆顶的元素出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。

为了方便判断堆顶元素与滑动窗口的位置关系，我们在堆中存储二元组 (num, index)，堆的元素是下标 index，权重是下标对应的值 num。

时间复杂度： 时间复杂度：O(nlog⁡n)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(log⁡n)，因此总时间复杂度为 O(nlog⁡n)。

空间复杂度： O(n)，即为优先队列需要使用的空间。

下面以 Golang 为例给出实现。

// a 表示数组，用于表示堆中元素的权重。
var a []int

// 堆，需要实现 heap.Interface 接口。
// 使用 []int 作为堆的存储结构，其中存储数组 nums 的下标。
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool  { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }

// 注意：heap 包的源码在 Pop 前会将堆顶元素与最后一个元素交换后再调用该函数。
func (h *hp) Pop() interface{}   { s := h.IntSlice; v := s[len(s)-1]; h.IntSlice = s[:len(s)-1]; return v }

func maxSlidingWindow(nums []int, k int) []int {
    a = nums
    q := &hp{make([]int, k)}
    for i := 0; i < k; i++ {
        q.IntSlice[i] = i
    }
    heap.Init(q)

    n := len(nums)
    r := make([]int, 1, n-k+1)
    r[0] = nums[q.IntSlice[0]]
    for i := k; i < n; i++ {
        heap.Push(q, i)
        // 当堆顶元素不在窗口中时不断弹出，直至堆顶的元素出现在滑动窗口中。
        for q.IntSlice[0] <= i-k {
            heap.Pop(q)
        }
        r = append(r, nums[q.IntSlice[0]])
    }
    return r
}

方法三：单调队列

能不能在线性时间内求解该问题呢？

我们可以通过一个单调队列保存当前窗口的最大值以及「在窗口最大值后面递减的值」。

为了便于判断队首元素是否超出窗口范围，所以队列中保存数组元素下标。

首先初始化第一个窗口对应的单调队列。遍历窗口元素：

如果大于等于队尾元素，则删除队尾元素，然后将元素下标存入队尾。
如果小于队尾元素，则直接入队列。

然后获取队首元素作为第一个窗口的最大值。
当滑动窗口向右移动时，我们需要把一个新的元素放入队列。放入方式与初始化第一个窗口对应的单调队列相同。
每移动一次窗口，都需要判断队首元素下标是否已经不在当前窗口，如果不在则移除。

为了可以同时弹出队首和队尾的元素，我们需要使用「双端队列」。

时间复杂度： O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。

空间复杂度： O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1 个元素，因此队列使用的空间为 O(k)。

下面以 Golang 为例给出实现：

func maxSlidingWindow(nums []int, k int) []int {
    // 双端队列。
    q := []int{}
    push := func(i int) {
        for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
            q = q[:len(q)-1]
        }
        q = append(q, i)
    }

    // 初始化第一个窗口对应的队列。
    for i := 0; i < k; i++ {
        push(i)
    }

    n := len(nums)
    r := make([]int, 1, n-k+1)
    r[0] = nums[q[0]]
    
    // 移动窗口。
    for i := k; i < n; i++ {
        push(i)
        // 如果队列首部元素下标不在窗口则移除。
        if q[0] <= i-k {
            q = q[1:]
        }
        r = append(r, nums[q[0]])
    }
    return r
}