[Leetcode 239] 滑动窗口最大值

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。
滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
 
示例 1:
示例 2:

解法一:最大堆

我们想要随时拿到当前窗口的最大值,可以使用最大堆的“堆顶即最大”的特性。
窗口在滑动,旧元素可能已经滑出窗口,所以需要能懒删除那些“已过期”的堆顶:过期的元素不急着删,等它蹦到堆顶再丢。
  • 堆里放二元组 (-nums[i], i)(用负号模拟大根堆),既能按值取最大,也能用索引判断是否过期。
  • 每次右移窗口:把新元素入堆,然后不停弹出堆顶,直到堆顶索引仍在当前窗口范围内;此时堆顶就是当前窗口最大值。
复杂度
  • 时间:O(n log n)(每个元素入堆一次,最坏弹出也近一次)
  • 空间:O(n)(堆最坏可堆满)

解法二:单调队列(最优解)

相邻窗口共享 k-1 个元素,只有一个新进的元素替代滑出的。
既然越新的、越大的值更有希望当最大,那凡是更旧且更小的元素,可以在进新元素时“当场淘汰”。
这就把“求最大值”变成了维护一个值单调递减的双端队列
具体步骤:
  • 队列中存元素的索引,对应的 nums[idx] 严格单调递减
  • 进新元素 j 时:不断弹出队尾所有比 nums[j] 小(或等于也可弹)的索引,再把 j 追加到队尾。
  • 窗口右移后,如队首索引已不在窗口内(<= i-k),就从队首弹出。
  • 队首索引对应的值就是窗口最大值——因为队列保持了“从大到小”的候选序。
复杂度
  • 时间:O(n)(每个索引最多入队一次、出队一次)
  • 空间:O(k)(队列里最多存一个窗口内的若干索引)

解法三:分块预处理

一次线性预处理,让每个长度为 k 的窗口都能在 O(1) 时间查询。
把数组按 k 分块:一个窗口要么完全落在某块,要么是前一块的后缀 + 下一块的前缀
  • 定义两张表:
    • prefixMax[i]:在本块内(从块头开始)到位置 i 的前缀最大;
    • suffixMax[i]:在本块内,从位置 i 到块尾的后缀最大。
  • 对任意窗口 [i, i+k-1]
    • 若跨块:答案是 max(suffixMax[i], prefixMax[i+k-1])
    • 若正好块对齐:等价于上式(两者都等于整块最大)。
复杂度
  • 时间:O(n)(两次线性扫描 + 一次组装)
  • 空间:O(n)(两张辅助表)
 
Buy Me a Coffee
上一篇
[Leetcode 236] 二叉树的最近公共祖先
下一篇
[Leetcode 240] 搜索二维矩阵 II