239. 滑动窗口最大值
题目简述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
思路：
1. 构建两个空列表，一个名为queue，用来存储元素在nums中的下标值；一个名为res，用来存储要输出的结果
2. 遍历nums中第1个元素，因为queue中为空，直接加进去即可
3. 遍历nums中第2个元素，用这个元素nums[2]与nums[queue[-1]]比较大小
4. 如果大于nums[queue[-1]]，那么把queue[-1]从queue中删除，把下标2放入queue中
5. 如果小于，不执行删除操作，也把下标2放入queue中
6. 在步骤5的条件下，遍历nums第3个元素，如果大于nums[queue[-1]]，执行步骤4中的把queue[-1]从queue中删除，然后继续判断nums[i]是否大于nums[queue[-1]]，直至queue最前面一个元素或者nums[i]小于nums[queue[-1]]
7. 当i==k-1了，此时需要往res加一个最大值，直接取nums[queue[0]]即可
8. 当i>k-1，此时queue[0]可能等于i-k了，如果等于，需要移除queue[0]；
9. 随后看看nums[i]是否大于nums[queue[-1]]，一直大于就一直删除queue[-1]，直至queue中没有元素了，把i加入queue中；如果中途有小于nums[queue[-1]]，就append进queue
10.重复9，直至遍历结束
代码如下：
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: # 如果数组为空或 k = 0，直接返回空 if not nums or not k: return [] # 如果数组只有1个元素，直接返回该元素 if len(nums) == 1: return [nums[0]] # 初始化队列和结果，队列存储数组的下标 queue = [] res = [] for i in range(len(nums)): # 如果当前队列最左侧存储的下标等于 i-k 的值，代表目前队列已满。 # 但是新元素需要进来，所以列表最左侧的下标出队列 if queue and queue[0] == i - k: queue.pop(0) # 对于新进入的元素，如果队列前面的数比它小，那么前面的都出队列 while queue and nums[queue[-1]] < nums[i]: queue.pop() # 新元素入队列 queue.append(i) # 当前的大值加入到结果数组中 if i >= k-1: res.append(nums[queue[0]]) return res
用collections.deque()构建双端队列更省时，代码如下：
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if k==1: return nums res=[] queue=collections.deque() for i in range(len(nums)): if queue and queue[0]==i-k: queue.popleft() while queue and nums[queue[-1]]<nums[i]: queue.pop() queue.append(i) if i>=k-1: res.append(nums[queue[0]]) return res
347.前K个高频元素
题目简述：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
思路：
快速排序
1. 记录每个数字出现的次数
2. 对每个数及对应次数通过快排进行排序，返回前k个
3. 快排步骤
i. 随机选一个中间值作为基准，并把它挪到最左侧
ii. 从第2个元素开始遍历，遍历过程中，要把比基准大的挪到左边，比基准小的挪到右边
iii. i 指向比基准大的元素，只要 j 指向的元素比基准小，就把 j 位置的元素和i后面一个位置的元素对调并且i后移一位，这样 i 指向的元素以及i之前的元素都是比基准大的元素（基准本身除外）
iv. j遍历到末尾后，此时i指向的就是排序后的列表中比基准大的最后一个元素，将该元素和基准对调，即
num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
这样排序后的列表就是在i位置前的都比 i 大，i 位置后的都比 i 小
4. 接下来就是分治部分了
i. 如果 i == k - 1，也就是i及之前的元素恰好组成了我们想要的topK，直接返回前k个元素
ii. 如果 i > k - 1, 也就是i及之前的元素组成了top(K+N)，要对前 i 个元素再进行一次快排，从top(K+N)里选出topK
findTopK(num_cnt, k, low, i - 1)
iii. 如果 i < k - 1，也就是i及之前的元素组成了top(K-N)，要对i之后的元素再进行快排，在之后的元素中选出topN
findTopK(num_cnt, k, i + 1, high)
5. 返回快排结果中的数字部分
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = collections.Counter(nums) num_cnt = list(count.items()) topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1) return [item[0] for item in topKs] def findTopK(self, num_cnt, k, low, high): pivot = random.randint(low, high) num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low] base = num_cnt[low][1] i = low for j in range(low + 1, high + 1): if num_cnt[j][1] > base: num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1] i += 1 num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low] if i == k - 1: return num_cnt[:k] elif i > k - 1: return self.findTopK(num_cnt, k, low, i - 1) else: return self.findTopK(num_cnt, k, i + 1, high)
总结
1. 对快排的理解还需要加深
2. collections包要熟练运用