题目简介
239: 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
初见思路
- 初见的时候想Python特性直接暴力解
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if len(nums) == 1:
return [nums[0]]
ans = list()
for i in range(len(nums) - k + 1):
window = nums[i:i+k]
window.sort()
ans.append(window[-1])
return ans
天真了，这样肯定超时；结合这两天的主题，应该是队列或者堆的方式，自然的我们会想维护一个单调的栈或队列。构建一个队列来记录窗口的最大值：
class MaxQueue:
def __init__(self):
self.queue = deque()
def front(self):
return self.queue[0]
def push(self,val):
while self.queue and val > self.queue[-1]:
self.queue.pop()
self.queue.append(val)
def pop(self,val):
if self.queue and val == self.queue[0]:
self.queue.popleft()
结合这个单调队列，可以得到下方的解：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = MaxQueue()
ans = list()
for i in range(k):
q.push(nums[i])
ans.append(q.front())
for i in range(k,len(nums)):
q.pop(nums[i - k])
q.push(nums[i])
ans.append(q.front())
return ans
- 其实这道题不涉及栈和队列的知识的知识也能暴力解出来，用字典。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
hash_map = dict()
for num in nums:
hash_map[num] = hash_map.get(num,0) + 1
ans = list()
i = 0
for key,val in sorted(hash_map.items(),key=lambda x:-x[1]):
if i == k: break
ans.append(key)
i += 1
return ans
复盘思路
在LC上对239有一种优化思路，我们可以简化队列存储的内容，实际上存储元素的下标就可以了：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k<=0:
return []
res = []
q = collections.deque()
for i in range(len(nums)):
if q and i-k == q[0]:
q.popleft()
while q and nums[i]>nums[q[-1]]:
q.pop()
q.append(i)
if i>=k-1:
res.append(nums[q[0]])
return res
对于347，随想录给出的解法主要是教导人们heapq的用法：
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
#要统计元素出现频率
map_ = {} #nums[i]:对应出现的次数
for i in range(len(nums)):
map_[nums[i]] = map_.get(nums[i], 0) + 1
#对频率排序
#定义一个小顶堆，大小为k
pri_que = [] #小顶堆
#用固定大小为k的小顶堆，扫描所有频率的数值
for key, freq in map_.items():
heapq.heappush(pri_que, (freq, key))
if len(pri_que) > k:
heapq.heappop(pri_que)
print(pri_que)
#找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
result = [0] * k
for i in range(k-1, -1, -1):
result[i] = heapq.heappop(pri_que)[1]
return result
重点难点
https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
今日收获
- 单调队列
- Python中堆的使用 - heapq
