day12

1、leetcode239 滑动窗口最大值

1. 思路：

   1. 使用一个队列，将窗口里的元素放入队列，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
      1. 队列所需操作：pop、push、getMaxValue
   2. 这个队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的
      1. 维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。
   3. 设计
      1. 在出口处（队首）维护最大值
         1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素（队首），那么队列弹出元素，否则不用任何操作【确保移除元素是最大值】
         2. push(value)：如果push的元素value大于入口元素（队尾）的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止【确保队列元素是单调排列】
         3. getMaxValue()：出口处元素即为当前窗口最大值

2. 代码实现

   class Solution {
       public int[] maxSlidingWindow(int[] nums, int k) {
           MyQueue que = new MyQueue();
           int[] res = new int[nums.length-k+1];
           int index = 0;
   
           for(int i=0; i<k; i++){ // 先将前k的元素放进队列
               que.push(nums[i]);
           }
           res[index++] = que.getMaxValue();// result 记录前k的元素的最大值
   
           for(int i=k; i<nums.length; i++){
               que.pop(nums[i-k]); // 滑动窗口移除最前面元素
               que.push(nums[i]); // 滑动窗口前加入最后面的元素
               res[index++] = que.getMaxValue(); // 记录对应的最大值
           }
   
           return res;
       }
       
   }
   
   class MyQueue { 
       Deque<Integer> deque  = new LinkedList<Integer>();
       
       void pop(int val){
           if(!deque.isEmpty() && val==deque.peek()){
               deque.poll();
           }
       }
   
       void push(int val){
           while(!deque.isEmpty() && val > deque.peekLast()){
               deque.pollLast();
           }
           deque.offer(val);
       }
   
       int getMaxValue(){
           return deque.peek();
       }
   }
   

2、leetcode347 前k个高频元素

1. 思路

   1. 遍历数组，用map存储数组元素(key)以及其出现频次(value)
      1. 遍历map，用小顶堆统计最大的前k个元素
         1. 只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

2. 代码实现

   class Solution {
       public int[] topKFrequent(int[] nums, int k) {
           Map<Integer, Integer> map = new HashMap<>(); //key为数组元素，value为出现频次
           for(int num : nums){
               map.put(num,map.getOrDefault(num,0)+1);
           }
           //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
           //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
           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;
   
       }
   }