java算法day10

• 239滑动窗口最大值
• 347前k个高频元素

---

239滑动窗口最大值

看灵神的题解学会的

精髓就在这张图
这个题用到了单调队列。首先知道为什么要使用单调队列，从这个问题来知道单调队列的好处。
首先就是我们模拟的窗口。滑动的这个过程显然就是一个队列元素出队进队的过程。但是现在我们需要一个附加条件，就是需要在每次移动之后，队列告诉我们里面的最大值是什么。
所以这就是单调队列的用武之地，单调队列的队顶到队尾是递减关系。

这个解法就是用双端队列ArrayDeque来模拟单调队列。用ArrayDeque来模拟就是因为他有方法可以直接获取队列中的最大元素，因为最大元素就在某一侧，可以用poll方法来进行获取。

注意：
1.既然是单调队列，那么队列中就要一直保持单调递减。
2.队列里存的并不是元素本身，而是元素的索引。存索引也是为了方便队头元素的弹出。

模拟思路：

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;//结果集就是数组总长减去窗口长度+1，+1是因为窗口刚好覆盖的地方也是结果。int[] ans = new int[n-k+1];Deque<Integer> q = new ArrayDeque<>();for(int i = 0;i<n;i++){//入，入的时候要比较队尾，因为要保持单调队列的特征，一旦队尾元素比即将入队的元素小，那就直接弹出，弹出的原因就是，有这个即将入队的元素在，比该元素小的元素就没有成为最大值的可能。这也与单调队列的理念不谋而合。一旦队列空了，那也没必要比了，就直接入。
while(!q.isEmpty()&&nums[q.peekLast()]<=nums[i]){q.pollLast();}q.offerLast(i);//出。出只发生在队头，一旦当前索引-队头索引=k，注意一定要等，自己模拟一下，试想窗口为3，3-0的情况。队头直接弹出。if(i-q.peekFirst()>=k){q.pollFirst();}//记录答案//因为是从数组的一开始才进行进队操作，所以在i>=k-1，即窗口还没覆盖数组之前是没必要记录答案的，覆盖之后才用记录答案。所以这个放在这里也是因为，前面已经完成了入队和出队操作，i>=k-1就是窗口刚好覆盖数组的时候，所以取队顶（最大值）加入结果集。if(i>=k-1){ans[i-k+1] = nums[q.peekFirst()];}}return ans;}
}

---

347前k个高频元素

这题学了优先队列。
首先java中已经实现了优先队列。PriorityQueue，在了解了之后，发现，这东西本质其实就是个堆。

优先队列补充

PriorityQueue 在 Java 中的实现和使用：

内部实现：
PriorityQueue 是 Java 标准库中已经实现好的数据结构。
它默认使用最小堆（小根堆）实现。

定义比较器：
您可以通过提供一个自定义的 Comparator 来改变 PriorityQueue 的行为。
这个 Comparator 定义了元素之间的优先级关系。

大根堆 vs 小根堆：
默认（不提供 Comparator）：小根堆
提供自定义 Comparator：可以实现大根堆或其他自定义优先级
使用示例：

// 默认小根堆
PriorityQueue minHeap = new PriorityQueue<>();

// 大根堆
PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b - a);

// 自定义对象的优先队列
PriorityQueue pq = new PriorityQueue<>((p1, p2) -> p1.getAge() - p2.getAge());

关键点：
您不需要自己实现堆的底层逻辑（如上浮、下沉等操作）。
您只需要定义元素之间的优先级关系。
PriorityQueue 会根据您提供的比较逻辑自动维护堆的性质。

常用方法：
offer(E e): 添加元素
poll(): 移除并返回队首元素（最高优先级）
peek(): 返回队首元素但不移除
size(): 返回队列中的元素个数

性能：
插入和删除操作的时间复杂度为 O(log n)
因为有调整操作，才导致了他O(logn)。
访问队首元素的时间复杂度为 O(1)

总结：PriorityQueue 确实是 Java 已经实现好的，您只需要根据需要定义比较器来决定优先级的顺序（是大根堆还是小根堆，或其他自定义优先级）。这大大简化了在需要优先队列的场景中的编程工作。

比较器补充

关于比较器，我的建议是里面的compare规则记下来就好。不用去深究。
1.比较器的用处：
就是用来维护堆的性质的，因为比较器，才定义了是大顶堆还是小顶堆。每次插入或删除操作之后，它都会确保堆顶元素是当前堆中最小的元素。
2.如何定义：
直接记下来

基本规则：
o1 - o2 > 0：o1 排在 o2 后面
o1 - o2 < 0：o1 排在 o2 前面
o1 - o2 = 0：o1 和 o2 相等，顺序无关紧要
升序排序： 直接使用 o1 - o2 的逻辑

降序排序： 反转比较逻辑，使用 o2 - o1

实际应用：

// 升序
(o1, o2) -> o1.getSomeValue() - o2.getSomeValue()

// 降序
(o1, o2) -> o2.getSomeValue() - o1.getSomeValue()

注意事项：
对于整数比较，直接相减可能导致溢出，可以使用 Integer.compare()
对于浮点数，使用 Double.compare() 或 Float.compare()
对于字符串，可以直接使用 String.compareTo()
复杂比较： 对于多字段比较，可以组合多个比较结果

我下面定义小顶堆的完整写法

PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<Integer,Integer>>() {@Overridepublic int compare(Map.Entry<Integer,Integer> o1, Map.Entry<Integer,Integer> o2) {return o1.getValue() - o2.getValue();}}
);

怎么看出他是定义小顶堆，直接从比较器看，大于0表示o1排o2后面，所以排前面的就是小的。所以从维护的这个堆来看，小的排前面，那就是堆顶排最前面所以是小顶堆。

---

解题思路：
创建一个大小为k的小顶堆，然后将map里的元素加入小顶堆当中，在遍历map的过程中，频次小的就会弹出，最终频次大的会留在堆中。然后把堆里面的元素弹出，收集结果就行了。

class Solution {public int[] topKFrequent(int[] nums, int k) {//结果集int[] result = new int[k];//弄一个map用于统计频次HashMap<Integer,Integer> map = new HashMap<>();//遍历统计频次for(int num : nums){map.put(num,map.getOrDefault(num,0)+1);}//遍历map。Set<Map.Entry<Integer,Integer>> entries = map.entrySet();//搞一个小顶堆，必须是小顶堆。PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((o1,o2)-> o1.getValue()-o2.getValue());for(Map.Entry<Integer,Integer> entry : entries){//每次都要入队。queue.offer(entry);//入完队，要检查队列是不是超k个了，因为要始终维护一个长度为k的优先队列。//超了就弹出if(queue.size()>k){queue.poll();}}//一边弹出，一边收集结果。for(int i = k-1;i>=0;i--){result[i] = queue.poll().getKey();}return result;}
}