这道题用到了双端队列
既可以做队列也可以做栈
队列相关操作
poll:弹出队头元素
peek:查看队头
add:队尾添加元素
removeLast :删除队尾元素
解题思路:
23516
单调队列,push操作的时候,val和最后一个元素比,大的话,就循环移除last
比如
2
push3 >2? ? 3
push5>3? ?5
push1<5? 51
push6>1? 移除1? ?6>5移除6
get操作:
刚才的push逻辑可以看出,get的时候一定是最大值。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int [] res = new int[nums.length-k+1];
int index = 0;
MyQueue queue = new MyQueue();
for (int i = 0; i < k; i++) {
queue.add(nums[i]);
}
res[index++] = queue.peek();
// 1 2 3 4
for (int i = k; i < nums.length; i++) {
queue.poll(nums[i-k]);
queue.add(nums[i]);
res[index++] = queue.peek();
}
return res;
}
}
class MyQueue{
Deque<Integer> deque = new LinkedList<>();
void poll(int val){
if (!deque.isEmpty()&&val==deque.peek()){
deque.poll();
}
}
void add(int val){
while (!deque.isEmpty()&&val>deque.getLast()){
deque.removeLast();
}
deque.add(val);
}
int peek(){
return deque.peek();
}
}
这道题并不难,就是理解好什么是大顶堆,建议自己去手写大顶堆,堆排序,topK问题这些基础的操作还是要会的,java的优先级队列好像不能指定堆的大小,所以需要在循环里指定一下。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 数组的0是数组,1是频率
PriorityQueue<int []> queue = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
HashMap<Integer, Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
for( Map.Entry<Integer, Integer> x: map.entrySet()){
Integer key = x.getKey();
Integer value = x.getValue();
queue.add(new int[]{key,value});
//保留前k个频率最高
if(queue.size()>k){
queue.poll();
}
}
int [] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.poll()[0];
}
return res;
}
}
这是卡哥总结的,我总结就是注意下面这些地方
对于java,Deque就是卡哥说的双端队列,这一个队列就可以做栈和队列两个结构的操作,还很方便,头尾都能操作,就很方便写题以及项目中相关操作。
对于栈,注意栈的结构做一下巧妙的消除,可以回顾前面的题来理解这个思想。
对于队列的话,好像没什么需要注意的,就是注意滑动窗口这个的思想以及大顶堆这个数据结构
在大数据领域,堆还是很好的,因为比如100亿数据想要找到TOPK的值,对于绝大多数数据结构基本内存扛不住的,但是大顶堆、小顶堆只需要k个空间就可以了。java语言可以参考优先级队列直接调用,做题的时候不用手敲了我认为。联系的时候可以敲一下。
另外,对于程序,网页,怎么用到栈这样的结构的,java的调用栈,一层一层弹入,返回上一级,弹出,可以做一下这道题。
71. 简化路径
力扣71题,刷题的时候可以看。