239. 滑动窗口最大值
本题需要使用双端队列,因为队头和队尾都有可能弹出元素,因此使用deque
(1)直接写,不定义类
下面代码中,队列存放的是索引
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if len(nums) < k:
return None
res = []
# 维护一个单调递减的队列,队列中需要存放索引
# 初始化
queue = deque()
for i in range(k):
while queue and nums[i] > nums[queue[-1]]:
queue.pop()
queue.append(i)
res.append(nums[queue[0]])
for i in range(k, len(nums)):
while queue and queue[0] <= i - k:
queue.popleft()
while queue and nums[i] > nums[queue[-1]]:
queue.pop()
queue.append(i)
res.append(nums[queue[0]])
return res
nums[i] > nums[queue[-1]]: # >=也可以,因为存储的是索引
(2)构造一个单调队列的类
里面存储的是值
pop函数,虽然删除的是值,但是在相等的元素也存储的情况下并不会删错,因为队列是单调递减的,如果后面的值比之大,则不存在该值;如果后面的值比之小,也不会影响该值;如果后面的值等于该值,则两个值要么都保留,要么都被弹出去了,因此也没影响
from collections import deque
class MyQueue:
def __init__(self):
self.queue = deque()
def pop(self, value):
if self.queue and self.queue[0] == value:
self.queue.popleft()
def push(self, value):
while self.queue and self.queue[-1] < value: # 加上 = 就错误了 [-7,-8,7,5,7,1,6,0]
self.queue.pop()
self.queue.append(value)
def front(self):
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
queue = MyQueue()
for i in range(k):
queue.push(nums[i])
res.append(queue.front())
for i in range(k, len(nums)):
queue.pop(nums[i - k])
queue.push(nums[i])
res.append(queue.front())
return res
注意:存储数值时,单调递减的队列,一定要存储相等元素,不能弹出,不然可能删除错误
347.前 K 个高频元素
暴力解法:统计每个元素的频率,然后排序找出前K个
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
mapping = dict()
for num in nums:
mapping[num] = mapping.get(num, 0) + 1
sorted_map = sorted(mapping.items(), key=lambda x: x[1], reverse=True)
res = []
for i in range(k):
res.append(sorted_map[i][0])
return res
使用小顶堆实现,维持一个大小为K的小顶堆。heapq默认为小顶堆,可以用取负数的方式实现大顶堆
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
mapping = dict()
for num in nums:
mapping[num] = mapping.get(num, 0) + 1
heap = []
for num, freq in mapping.items():
if len(heap) >= k:
if freq > heap[0][0]:
heapq.heapreplace(heap, (freq, num))
else:
heapq.heappush(heap, (freq, num))
return [item[1] for item in heap]