直接的做法是遍历(n-k)个长度为k的数组，复杂度为O(n*k)。
优化的关键在于如何快速得到长度为k的数组内的最大值。
- 一种思路是使用最大堆。最大堆的最大值查询复杂度为O(1)，更新复杂度为O(log(n))。
import heapq
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if k == 1:
return nums
# 这里使用负数因为python默认为最小堆
Q = [(-nums[i],i) for i in range(k)]
# 建堆
heapq.heapify(Q)
ans = []
ans.append(-Q[0][0])
# 遍历之后的 `n-k`个数
idx = k
while idx < len(nums):
# push元素
heapq.heappush(Q, (-nums[idx], idx))
# pop直到最大值在当前的窗口内
while idx - Q[0][1] >= k:
heapq.heappop(Q)
ans.append(-Q[0][0])
idx += 1
return ans
这里学习一下heapq的常用接口：
heappush(heap, item):将item加入heap中，并保持堆的特征
heappop(heap): 弹出堆的最小值
heappushpop(heap, item): 将item加入堆中，并弹出最小值
heapify(x):建堆
heapreplace(heap, item): 弹出最小值，并插入新值。过程保持堆大小不变
- 优化方案是使用单调队列
单调队列的思路来源于：i < jandnums[i] < nums[j]=>只要i在队列中，j也在队列中
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if k == 1:
return nums
# 创建优先队列
Q = deque()
# 窗口初始化
for i in range(k):
# 逐渐递减的优先队列
while len(Q) > 0 and nums[i] > Q[-1][1]:
Q.pop()
# 加入新元素
Q.append((i, nums[i]))
ans = []
ans.append(Q[0][1])
for i in range(k, len(nums)):
# 加入新元素前，保持优先队列的递减性
while len(Q) > 0 and nums[i] > Q[-1][1]:
Q.pop()
# 确保第一个元素的下标在队列中
while len(Q) > 0 and i - Q[0][0] >= k:
Q.popleft()
# 由于递减特性，队列第一个值即最大值
Q.append((i, nums[i]))
ans.append(Q[0][1])
return ans
这里学习一下collections常见的工具：
- deque
类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)
append(): 末尾添加元素
appendleft(): 添加 x 到左端。
clear(): 移除所有元素，使其长度为0。
copy(): 创建一份浅拷贝。
extend(list): 扩展deque的右侧
insert(idx, item):在位置 i 插入 x 。
pop(): 移去并且返回一个元素，deque 最右侧的那一个。
popleft():移去并且返回一个元素，deque 最左侧的那一个。
reverse():将deque逆序排列。
- Counter
字典的子类，提供了可哈希对象的计数功能。
constructor(iter): 从可迭代的对象中创建一个计数器
elements(): 返回数据中出现的所有元素的集合
most_common(topk): 返回数据中最频繁的topk个元素
subtract(counter):体重一种计数器之间相减的方法
update([iterable-or-mapping]):更新计数器
- defaultdict
在字典中获取一个 key 有两种方法, 第一种 get , 第二种 通过 [] 获取.
使用dict时，如果引用的Key不存在，就会抛出KeyError。
如果希望key不存在时，返回一个默认值，就可以用defaultdict。
