一、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博客
三、今日小结
最近好疲劳啊,今天补了昨天的遗漏,吃个饭饭开启下一篇 ^*^