代码随想录算法训练营第十三天|单调数列：滑动窗口最大值(力扣239.)、优先级队列：前k个高频元素(力扣347.)

单调数列：滑动窗口最大值(力扣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;
    }
}