这道题用到了双端队列
既可以做队列也可以做栈
队列相关操作
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题，刷题的时候可以看。