代码随想录
LeetCode 239. 滑动窗口最大值
优先级队列 #单调队列
思路
- 优先级队列解法：
- 窗口移动过程中，不断将新元素加入优先级队列，如果最大值不在范围内，则弹出最大值
- $$T(n) = O(nlogn)$$
- $$S(n) = O(n)$$
- 单调队列解法：
- 实现一种数据结构，每次移动后，都能直接访问到当前最大
- 选用队列结构，让队首元素是当前最大
- 实现上一条，需要保证每次移动后队列都是单调递减，这样才能保证队首元素永远是当前最大值
- 单调队列队首是确定的最大值，其他元素是当前已知信息下有可能作为最大值的元素，每次移动都会排除确定不能成为最大值的元素
$$T(n) = O(n)$$
$$S(n)=O(k)$$
细节
- 实现一种数据结构，每次移动后，都能直接访问到当前最大
- 如何更新数据结构
- 如何实现单调队列
LeetCode 347. 前 K 个高频元素
优先级队列 #模板 #比较函数 #大顶堆 #小顶堆
思路
- 遍历保存所有元素的频数 ---> 哈希
- 频数排序 ---> 优先级队列
细节
-
哈希中KV是 元素 - 频数
-
堆中KV要按频数排序，两种思路：
- 把哈希中的KV对调存入堆中
- 修改优先级队列的比较函数
-
优化：
-
上面是堆的保存所有元素，且排序所有元素，可以考虑堆大小保持为k，每次更新最小元素
- 这种方式能降低时间复杂度之前$$O(NlogN)$$ 优化后$$O(Nlogk)$$
- 并降低空间占用，由于更新最小元素，只能使用小顶堆
-
对调
![[Pasted image 20221024232318.png]] -
重写比较函数
LeetCode或随想录
![[Pasted image 20221024232554.png]]
![[Pasted image 20221024232441.png]]