一、LeetCode 239 滑动窗口最大值

题目链接：239.滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/

思路：使用单调队列，只保存窗口中可能存在的最大值，从而降低时间复杂度。

public class MyQueue{Deque<Integer> queue = new LinkedList<>();//弹出元素时，判断要窗口弹出的数值是否等于队列出口的数值void poll(int val){if(!queue.isEmpty() && val == queue.peek()){queue.poll();}}//添加元素时，判断要添加的元素是否大于队列入口处的元素//如果大于，就将入口处元素弹出，保证队列单调递减void offer(int val){while(!queue.isEmpty() && val > queue.getLast()){queue.removeLast();}queue.offer(val);}//栈顶始终为最大值int peek(){return queue.peek();}
}
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length == 1){return nums;}int len = nums.length - k + 1;int[] ans = new int[len];int index = 0;MyQueue queue = new MyQueue();//先把前k个元素入队for(int i = 0; i < k; i++){queue.offer(nums[i]);}//记录前k个元素中的最大值ans[index++] = queue.peek();for(int i = k; i < nums.length; i++){//弹出 + 入队queue.poll(nums[i-k]);queue.offer(nums[i]);//记录每组窗口的最大值ans[index++] = queue.peek();}return ans;}
}

 二、LeetCode 347 前k个高频元素

题目链接：347.前k个高频元素https://leetcode.cn/problems/top-k-frequent-elements/

思路：维护大小为k的小顶堆，遍历map<元素,出现次数>每次弹出出现次数最少的元素，最终得到出现次数前k的元素。

class Solution {public int[] topKFrequent(int[] nums, int k) {//基于小顶堆实现Map<Integer,Integer> map = new HashMap<>();for(int a : nums){map.put(a,map.getOrDefault(a,0) + 1);}//在优先队列里存储二元组 出现次数低的在队头PriorityQueue<int[]> pq = new PriorityQueue<>((p1,p2) -> p1[1]-p2[1]);//map.Entry是键值对for(Map.Entry<Integer,Integer> entry : map.entrySet()){//pq的元素个数小于k，直接添加if(pq.size() < k){pq.add(new int[]{entry.getKey(),entry.getValue()});}else{//当前元素出现次数大于pq队头(小顶堆堆顶)元素if(entry.getValue() > pq.peek()[1]){pq.poll();pq.add(new int[]{entry.getKey(),entry.getValue()});}}}int[] ans = new int[k];for(int i = 0; i < k; i++){ans[i] = pq.poll()[0];}return ans;}
}

补充：重写comparTo()方法 -- (a1,a2)->(a1-a2)为按递增顺序排列

参考文章：Java 优先级队列-CSDN博客

三、今日小结

        最近好疲劳啊，今天补了昨天的遗漏，吃个饭饭开启下一篇 ^*^