基础知识
ArrayDeque deque = new ArrayDeque();
/*
offerFirst(E e) 在数组前面添加元素，并返回是否添加成功
offerLast(E e) 在数组后天添加元素，并返回是否添加成功
pollFirst()删除第一个元素，并返回删除元素的值，如果元素为null，将返回null
pollLast()删除最后一个元素，并返回删除元素的值，如果为null，将返回null
getFirst() 获取第一个元素,如果没有将抛出异常
getLast() 获取最后一个元素，如果没有将抛出异常
toArray() 转成数组
contains(Object o) 判断队列中是否存在该元素
size() 获取队列中元素个数
isEmpty() 判断队列是否为空
队列操作 offer poll peek
栈操作 push pop peek
*/
PriorityQueue
PriorityQueue<Object> pq = new PriorityQueue<>((o1, o2)->o1.xxx-o1.xxx);
// offer poll size toArray contains peek
// Map遍历 效率更高
for (Map.Entry<String, String> entry : myMap.entrySet()) {
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}LeetCode 239. 滑动窗口最大值
分析1.0
遍历数组添加新元素时，要维护一个队列，保证队列元素递减-单调递减队列
失误
不要想着把窗口中的元素全部放进队列再去找最大值
分析2.0
- 首先要将前k个元素按照push原则入队，之后取队首元素
pop(value)：如果窗口移除的元素value等于单调队列的出口元素（使用索引），那么队列弹出元素，否则不用任何操作
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
这个要在容器的两头操作，没搞清楚数据结构，用普通队列操作实在是...欲哭无泪，内心愤怒值+++++++++
class Solution {
ArrayDeque<Integer> queue = new ArrayDeque();
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length - k + 1;
int[] res = new int[len];
for(int i = 0; i < k; i++){
// queue不为空 而且首元素小于当前元素时
while(!queue.isEmpty() && nums[queue.peek()] <= nums[i]){
queue.poll();
}
while(!queue.isEmpty() && nums[queue.getLast()] <= nums[i]){
queue.pollLast();
}
queue.offer(i);
}// 前k个元素索引入队
// 后nums.length - k 个元素入队
int inIndex = k, outIndex = 0, index = 0;
res[index++] = nums[queue.peek()];
while(index < len){
addElem(nums, inIndex++, outIndex++);
res[index++] = nums[queue.peek()];
}
return res;
}
public void addElem(int[] nums, int inIndex, int outIndex){
// 要出栈的元素是队首元素的话-通过数组索引锁定
if(!queue.isEmpty() && queue.peek() == outIndex){
queue.poll();
}
while(!queue.isEmpty() && nums[queue.getLast()] <= nums[inIndex]){
queue.pollLast();
}
queue.offer(inIndex);
}
}LeetCode 347.前 K 个高频元素
分析1.0
Map<元素value，出现频率> ，按照频率降序排序，输出前k个key 或者是在每次遍历数组修改map时，维护map顺序，
维护Map顺序考虑工具 堆 或者 自己实现算法
class Solution {
//解法1：基于大顶堆实现
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//大顶堆需要对所有元素进行排序
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
int[] ans = new int[k];
for(int i=0;i<k;i++){//依次从队头弹出k个,就是出现频率前k高的元素
ans[i] = pq.poll()[0];
}
return ans;
}
}总结
- 在进行栈、队列等容器操作时，要先判断容器是否为空
循环首先要确认终止条件、避免常见的ArrayOutOfIndex错误
PriorityQueue 实现自定义比较器，构造器参数不能为Map
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch
