。

这种特性使得单调队列在处理一些问题时非常高效#…简要介绍一下单调队列和优先级队列的不同

元素顺序的处理单调队列中元素的顺序是单调的也就是说队列中的元素按照特定的单调性递增或递减排列。

这种特性使得单调队列在处理一些问题时非常高效例如寻找滑动窗口中的最大值或最小值。

优先队列则根据元素的优先级进行排序优先级高的元素先出队。

优先队列并不保证元素的单调性。

入队和出队的操作在单调队列中元素可以从队尾入队但出队操作只能在队首进行。

这是因为单调队列需要保持其单调性所以新加入的元素需要放在合适的位置以维持这种单调性。

优先队列则允许元素从任意位置入队出队操作则总是发生在优先级最高的元素上。

队列长度单调队列的长度取决于输入数据的合法性如果输入数据不满足单调性要求那么队列长度就可能为0。

而优先队列的长度则始终与输入数据的数量等同因为所有输入数据都会被放入队列中只是出队的顺序会根据优先级有所不同。

(programmercarl.com)

这道题有点难度,我们如果使用暴力求解的话是跑不过的,暴力方式就是遍历全部的数组,再遍历每K个元素的滑动窗口,分别找出最大值放入返回数组,这里我们不使用这个方式.

add方法:如果队尾元素比传入元素小,删除该元素,保证前方元素都大于我要传入的元素,从而保证单调队列的单调性

peek方法:因为单调队列维护了队头的最大元素,peek用来返回队头元素

2.实现函数

首先创建单调队列,先将前k个元素传入单调队列,获取其最大值,对k到数组结束的元素进行以下处理,先poll前k个元素,加入新的元素,比较得到最大值,最后返回最大值数组即可.

代码实现

valque.getLast()){que.removeLast();}que.add(val);}int

peek(){return

0;ik;i){que.add(nums[i]);}res[num]

que.peek();for(int

k;ilen;i){que.poll(nums[i-k]);que.add(nums[i]);res[num]

que.peek();

首先创建一个map,key用来放置元素,value用来存放出现频率,这题我们就用到了优先级队列了,因为我们想用低于快排的时间复杂度解决问题,我们就只能使用大顶堆或小顶堆的数据结构,维护一个k个元素的堆来解决问题,最后将前k个元素依次pop出来即可.(这里为了简化代码使用了lambda表达式)

代码实现

HashMap();//key为数组元素值,val为对应出现次数for(int

num:nums){map.put(num,map.getOrDefault(num,0)1);}//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)PriorityQueueint[]

new

pair2)-pair2[1]-pair1[1]);for(Map.EntryInteger,Integer

entry:map.entrySet()){//大顶堆需要对所有元素进行排序pq.add(new

int[]{entry.getKey(),entry.getValue()});}int[]

ans

i0;ik;i){//依次从队头弹出k个,就是出现频率前k高的元素ans[i]

pq.poll()[0];}return

HashMap();//key为数组元素值,val为对应出现次数for(int

num:nums){map.put(num,map.getOrDefault(num,0)1);}//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数//出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)PriorityQueueint[]

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

ik-1;i0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多ans[i]

pq.poll()[0];}return

x.getValue();pq.offer(tmp);if(pq.size()

{pq.poll();}}for(int