集团网站建设哪个好,广州企业招聘,如何做分享赚钱的网站,深圳购物网站建设报价简要介绍一下单调队列和优先级队列的不同 元素顺序的处理#xff1a;单调队列中#xff0c;元素的顺序是单调的#xff0c;也就是说#xff0c;队列中的元素按照特定的单调性#xff08;递增或递减#xff09;排列。这种特性使得单调队列在处理一些问题时非常高效#…简要介绍一下单调队列和优先级队列的不同 元素顺序的处理单调队列中元素的顺序是单调的也就是说队列中的元素按照特定的单调性递增或递减排列。这种特性使得单调队列在处理一些问题时非常高效例如寻找滑动窗口中的最大值或最小值。优先队列则根据元素的优先级进行排序优先级高的元素先出队。优先队列并不保证元素的单调性。入队和出队的操作在单调队列中元素可以从队尾入队但出队操作只能在队首进行。这是因为单调队列需要保持其单调性所以新加入的元素需要放在合适的位置以维持这种单调性。优先队列则允许元素从任意位置入队出队操作则总是发生在优先级最高的元素上。队列长度单调队列的长度取决于输入数据的合法性如果输入数据不满足单调性要求那么队列长度就可能为0。而优先队列的长度则始终与输入数据的数量等同因为所有输入数据都会被放入队列中只是出队的顺序会根据优先级有所不同。 更详细的题解和思路:代码随想录 (programmercarl.com)
LeetCode T239 滑动窗口的最大值
题目链接:239. 滑动窗口最大值 - 力扣LeetCode 题目思路 这道题有点难度,我们如果使用暴力求解的话是跑不过的,暴力方式就是遍历全部的数组,再遍历每K个元素的滑动窗口,分别找出最大值放入返回数组,这里我们不使用这个方式. 我们使用单调队列而不是优先级队列 因为优先级队列只能将最大的元素选出来,而下一步操作 1.创建单调队列,定义add,peek,poll方法 poll方法:如果移除元素等于队列的出口元素,弹出该元素 add方法:如果队尾元素比传入元素小,删除该元素,保证前方元素都大于我要传入的元素,从而保证单调队列的单调性 peek方法:因为单调队列维护了队头的最大元素,peek用来返回队头元素 2.实现函数 首先创建单调队列,先将前k个元素传入单调队列,获取其最大值,对k到数组结束的元素进行以下处理,先poll前k个元素,加入新的元素,比较得到最大值,最后返回最大值数组即可. 代码实现
class MyQue{DequeInteger que new LinkedList();void poll(int val){if(!que.isEmpty() val que.peek()){que.poll();}}void add(int val){while(!que.isEmpty() valque.getLast()){que.removeLast();}que.add(val);}int peek(){return que.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length 1){return nums;}MyQue que new MyQue();int len nums.length;int num 0;int[] res new int[len-k1];for(int i 0;ik;i){que.add(nums[i]);}res[num] que.peek();for(int i k;ilen;i){que.poll(nums[i-k]);que.add(nums[i]);res[num] que.peek(); }return res;}
} LeetCode T347 前K个高频元素
题目链接:347. 前 K 个高频元素 - 力扣LeetCode 题目思路 首先创建一个map,key用来放置元素,value用来存放出现频率,这题我们就用到了优先级队列了,因为我们想用低于快排的时间复杂度解决问题,我们就只能使用大顶堆或小顶堆的数据结构,维护一个k个元素的堆来解决问题,最后将前k个元素依次pop出来即可.(这里为了简化代码使用了lambda表达式) 代码实现
class Solution {//解法1基于大顶堆实现public int[] topKFrequent(int[] nums, int k) {MapInteger,Integer map new HashMap();//key为数组元素值,val为对应出现次数for(int num:nums){map.put(num,map.getOrDefault(num,0)1);}//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)PriorityQueueint[] pq new PriorityQueue((pair1, pair2)-pair2[1]-pair1[1]);for(Map.EntryInteger,Integer entry:map.entrySet()){//大顶堆需要对所有元素进行排序pq.add(new int[]{entry.getKey(),entry.getValue()});}int[] ans new int[k];for(int i0;ik;i){//依次从队头弹出k个,就是出现频率前k高的元素ans[i] pq.poll()[0];}return ans;}
} //解法2基于小顶堆实现public int[] topKFrequent2(int[] nums, int k) {MapInteger,Integer map new HashMap();//key为数组元素值,val为对应出现次数for(int num:nums){map.put(num,map.getOrDefault(num,0)1);}//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)PriorityQueueint[] pq new PriorityQueue((pair1,pair2)-pair1[1]-pair2[1]);for(Map.EntryInteger,Integer entry:map.entrySet()){//小顶堆只需要维持k个元素有序if(pq.size()k){//小顶堆元素个数小于k个时直接加pq.add(new int[]{entry.getKey(),entry.getValue()});}else{if(entry.getValue()pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了pq.add(new int[]{entry.getKey(),entry.getValue()});}}}int[] ans new int[k];for(int ik-1;i0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多ans[i] pq.poll()[0];}return ans;
简化版代码(避免一些api)
class Solution {public int[] topKFrequent(int[] nums, int k) {// 优先级队列为了避免复杂 api 操作pq 存储数组// lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从大到小o2 - o1 反之PriorityQueueint[] pq new PriorityQueue((o1, o2) - o1[1] - o2[1]);int[] res new int[k]; // 答案数组为 k 个元素MapInteger, Integer map new HashMap(); // 记录元素出现次数for(int num : nums) map.put(num, map.getOrDefault(num, 0) 1);for(var x : map.entrySet()) { // entrySet 获取 k-v Set 集合// 将 kv 转化成数组int[] tmp new int[2];tmp[0] x.getKey();tmp[1] x.getValue();pq.offer(tmp);if(pq.size() k) {pq.poll();}}for(int i 0; i k; i ) {res[i] pq.poll()[0]; // 获取优先队列里的元素}return res;}
}
