单调数列：滑动窗口最大值(力扣239.)
- 给定滑动窗口的范围，求每个滑动窗口范围内的最大值
- 使用单调队列实现
- 对于最大值数字前面的数字不存入数列，对于最大值数字后面的数字存入数列中
- 单调队列中数字的大小呈递减顺序
- pop(value)：如果窗口移除的元素等于单调队列的队口元素，则pop；否则什么也不干
- push(value)：如果入口元素小于push的元素value，则一直弹出队尾元素，直到队尾元素大于等于push元素
- pop从队头走，push从对尾进
- 核心思想：只保留窗口内的有效元素，即较大值的排序较小的元素全部不进队列，并在每次push元素时保持队列的队头是此时最大值。
- 双端队列的api：获取队尾值：getLast();弹出队尾值removeLast();弹出队头值poll();
- 获取队头值且不弹出：peek();
class MyQueue{
Deque<Integer> deque = new LinkedList<>();
//弹出元素时，要考虑要弹出的元素是否为队头元素，如果是，则弹出；如果不是，则什么也不干
void poll(int val){
if(!deque.isEmpty()&&deque.peek()==val){
deque.poll();
}
}
//推入元素时，要考虑push的元素值是否都小于队尾元素，如果是，则直接push；如果不是，一直输出队尾元素
void push(int val){
while(!deque.isEmpty()&&deque.getLast() < val){
deque.removeLast();
}
deque.add(val);
}
//获取队头值且不弹出
int peek(){
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 1){
return nums;
}
int len = nums.length - k + 1;
int[] res = new int[len];
int num = 0;
//自定义队列
MyQueue myQueue = new MyQueue();
//先将前k个元素放入其中
for(int i = 0; i < k; i++){
myQueue.push(nums[i]);
}
res[num++] = myQueue.peek();
//将之后的元素放入
for(int j = k; j < nums.length;j++){
myQueue.poll(nums[j-k]);
myQueue.push(nums[j]);
res[num++] = myQueue.peek();
}
return res;
}
}
(仅理解思路)优先级队列：前k个高频元素(力扣347.)
- 题目：给定一个非空的整数数组，返回其中出现频率前k高的元素
- 涉及三块内容：1.统计元素出现频率 2. 对频率排序 3. 找出前k个高频元素
- 大顶堆和小顶堆：
- 堆的底层就是一个二叉树：大顶堆就是父树比它所有子树的值要大
- 优先级队列的底层实现方式就是堆
- 我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//基于小顶堆实现
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//用小顶堆实现
//优先队列PriorityQueue
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
for(Map.Entry<Integer,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 i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
ans[i] = pq.poll()[0];
}
return ans;
}
}