LeetCode 239 滑动窗口最大值

2021-02-12 2021-02-12 约 2150 字预计阅读 5 分钟

本题是一道典型的单调队列例题，其重点不在死记硬背解法代码，而在于深刻理解解法的构建思路，从而掌握单调队列的特性和使用方式。另外，本题也可以使用处理海量数据时常用的分块处理法，只是一定要注意分块方法要尽量简单，并保证可以正确、高效地应对跨区块的查询。

题目描述

原题链接如下： LeetCode 239. 滑动窗口最大值

题目大意

假设在一个整数数组 nums 上使用固定长度为 k 的滑动窗口扫描，每次窗口移动都会遇到新的数组子序列，而每个这样的子序列都有各自的最大值，要求输出所有这些最大值。

输入与输出

示例输入为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
Input 1:
nums = [1,3,-1,-3,5,3,6,7]
k = 3

Input 2:
nums = [1]
k = 1

Intput 3:
nums = [1,-1]
k = 1

Intput 4:
nums = [9,11]
k = 2

Intput 5:
nums = [4,-2]
k = 2

nums 和 k 的取值范围如下：
nums 的长度取值范围为 $[1, 100000]$
nums 的任意元素取值范围为 $[-10000, 10000]$
k 不会大于 nums 的长度

对应输出为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Output 1:
[3,3,5,5,6,7]

Output 2:
[1]

Output 3:
[1,-1]

Output 4:
[11]

Output 5:
[4]

解题思路

本题的暴力方法即模拟法，每次滑动窗口变化，就便利窗口内部的数据得出最大值。显然，如果使用暴力解法则时间复杂度是 $O(n^{2})$，在 n 可以取 100000 时效率太低，要想办法尽量降到 $O(n \log{n})$ 甚至 $O(n)$ 复杂度。

单调队列

先考虑暴力方法模拟为什么会超时？因为，滑动窗口移动时其实只新增加了一个元素，同时删除了一个元素，窗口“中间”的绝大部分元素都没有改变，那么至少这些没有改变的元素的最大值也不会变化。但是，暴力法无法重复利用这些没有改变的元素对应的最大值，所以重复运算较多、时间复杂度偏高。而毕竟涉及最大值的计算，很容易想到使用堆辅助计算，只要保存元素时同时存储位置信息即可，这样每次检查堆顶元素是否在当前窗口之内即可。可是，我们还应该想到其实每次检查堆顶元素，然后移除不在窗口的堆顶，我们都会对部分已经比较过的元素重新比较，只不过合理的树形结构使得重复比较较少罢了。再仔细观察滑动窗口的移动，我们不妨假设窗口内部有一对元素 nums[i] 与 nums[j]，满足 $i < j$，那么：

如果 $nums[i] > nums[j]$，则窗口右移使得 nums[i] 被移除时，无法立即确定剩余元素的最大值和 nums[i] 的关系
如果 $nums[i] \le nums[j]$，则即使 nums[i] 被移除，可以立即确定剩余元素最大值也至少不会小于 nums[j]

也就是说，我们如果要缓存元素，那么只需要缓存原数组内从左向右严格递减的元素即可，留待之后的计算，非严格递减的关系对结果无影响。即从左到右扫描滑动窗口的元素，构建缓存数据，保证其性质如下：

缓存的数据元素对应的数组下标从左向右是严格递增的
缓存的数据时从左向右严格递减

这样，第一次构建好缓存数据后，当前窗口对应的最大值就是最左侧的缓存数据。另外，一旦滑动窗口移动则会增加一个右侧元素，并移除一个左侧元素，我们需要保证缓存内增加和删除数据不改变上述约束条件：

增加数据时：不断移除缓存最右侧数据，直到新加入的数据满足严格递减约束
移除数据时：不断移除缓存最左数据，保证最左数据的下标在当前窗口内

第 2 步很好理解，因为之前的窗口对应的数据最大值可能就在最左边，那么旧的缓存数据也一定会在最左侧保存它，一旦窗口右移则必须剔除这个数据。而如果缓存最左侧就在当前窗口内那么说明旧的窗口最左侧的元素比当前最大值小，根本未被缓存。而第 1 步可行的原因是，一旦新加入窗口的最右侧元素比窗口内的部分元素大，那么那些之前缓存的较小的元素对当前以及之后窗口的最大值就再无任何影响，现在就可以把它们移出缓存。

这样，我们要使用的缓存数据结构要保证以下操作非常高效（即尽量是 $O(1)$ 时间复杂度）：

对数据在一侧进行添加和删除
另一侧进行删除和读取

所以，我们要使用一个双向队列缓存数据，并保证缓存数据严格单调递减。

分块法

我们如果把 nums 按照 k 个一组进行分组（最后一组元素可能不足 k 个），并且分别求初每个分组对应的最大值。那么如果我们求以 nums[i] 为最左边的窗口对应的最大值，那么可能有如下情况：

i 是 k 的倍数，那么分组时我们就求得了当前窗口对应的最大值
i 不是 k 的倍数，那么显然当前窗口横跨了两个分组，不能在分组时直接得出结果

对应第二种情况，不妨假设有 j 满足 $i < j < i + k$，那么此时窗口分为两部分：

前缀：$[i, j]$
后缀：$[j, i + k)$

只要我们能够预先算出各个下标对应的上述前缀、后缀的值，我们就可以求出所有窗口对应的最大值。当然，上述前后缀并不难求，只要使用如下递推公式即可：

前缀递推公式：

$$ prefix[i]= \begin{cases} nums[i]& \text{i 是 k 的倍数} \\ \max({prefix[i-1], nums[i]})& \text{i 不是 k 的倍数} \end{cases} $$

后缀递推公式：

$$ suffix[i]= \begin{cases} nums[i]& \text{i + 1 是 k 的倍数}\\ \max({suffix[i+1], nums[i]})& \text{i + 1 不是 k 的倍数} \end{cases} $$

注意：递推公式的起始条件如下：

prefix[0] = nums[0]
suffix[n - 1] = nums[n - 1]

这样，我们在对数据进行预处理之后，可以从左到右遍历数组：如果其下标 i 是 k 的倍数，那么任意取 suffix[i] 或 prefix[i+k-1] 均可：如果不是 k 的倍数，则是上述两数的最大值。所以，可以统一两种情况得到如下公式：

$$ max(i) = \max({suffix[i], prefix[i+k-1]}) $$

代码

单调队列：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.LinkedList

class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        if (k == 1) return nums
        val re = IntArray(nums.size - k + 1)
        val deque = LinkedList<Int>()
        repeat(k - 1) {
            while (deque.isNotEmpty() && nums[it] >= nums[deque.peekLast()]) deque.pollLast()
            deque.offerLast(it)
        }
        for (i in re.indices) {
            val t = i + k - 1
            while (deque.isNotEmpty() && nums[t] >= nums[deque.peekLast()]) deque.pollLast()
            deque.offerLast(t)
            while (deque.peekFirst() < i) deque.pollFirst()
            re[i] = nums[deque.peekFirst()]
        }
        return re
    }
}

分块法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val n = nums.size
        val preMax = IntArray(n)
        val sufMax = IntArray(n)
        for (i in nums.indices) {
            preMax[i] = if (i % k == 0) nums[i] else maxOf(preMax[i - 1], nums[i])
        }
        for (i in nums.indices.reversed()) {
            sufMax[i] = if (i == n - 1 || (i + 1) % k == 0) nums[i] else maxOf(sufMax[i + 1], nums[i])
        }
        val re = IntArray(n - k + 1)
        for (i in 0..n - k) {
            re[i] = maxOf(sufMax[i], preMax[i + k - 1])
        }
        return re
    }
}

目录