day10|239. 滑动窗口最大值、347.前 K 个高频元素_滑动窗口topk

239. 滑动窗口最大值        

        给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置                                   最大值

---------------                                            -----

[1    3   -1]    -3    5    3   6    7                 3

1    [3   -1     -3]   5    3   6    7                 3

1     3  [-1     -3    5]   3   6    7                 5

1     3   -1    [-3   5    3]   6    7                 5

1     3   -1     -3  [5    3    6]   7                 6

1     3   -1     -3   5   [3    6    7]                7

示例 2：

输入：nums = [1], k = 1

输出：[1]

 问题描述：

利用双端队列自己实现一个单调队列。 遍历整数数组，把数组下标依次加入队列，当队列加了一个下标代表的数，比之前代表的数都大， 那么就把队列中前面的下标全都移除，所以队列最前面的下标对应的数是最大值。 每当超过k的范围就把队列里最前面的下标移除。

 

class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            Deque<Integer> deque = new ArrayDeque<>();
            int[] res = new int[nums.length - k + 1];//找规律
            int index = 0;
            for (int i = 0; i < nums.length; i++) {//i为nums下标 队列放下标
 
                //如果队中元素，头与尾的距离比k大，则移除队头
                while (!deque.isEmpty() && deque.peek()<i-k+1) {//控制滑动窗口中遍历的范围，
                                                                 //每个窗口的队头为i-k+1
                    deque.removeFirst();
                }
                //如果此时要加入队列的元素比队尾元素大，则移除队尾元素
                while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                    deque.removeLast();
 
                }
                deque.addLast(i);
                //找滑动窗口选最大值的开始，例如k=2，则i到第二个位置就可以找出窗口的最大值
                if (i >= k - 1) {
                    res[index] = nums[deque.peekFirst()];
                    index++;
                }
            }
            return res;
        }
    }

这题有点ex，一开始队列存的是数而不是下标，结果就是，如果最大数在中间，完全移除不了，看了题解才知道要存下标，不然就得自己新写个队列，要写新方法，太麻烦果断放弃，直接改下标。orz 

---

 

347.前 K 个高频元素

          给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2:

输入: nums = [1], k = 1

输出: [1]

 问题分析：

先用map结构，key为值，value为出现次数。再把value从小到大排序，用小顶堆(PriorityQueue)实现，优先级队列存二元组pq[0]为值，pq[1]为出现次数。当小顶堆的元素数量>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);//若没有出现过则为0，若有则+1
        }
        //在优先队列存二元组<num,cs>,cs为在数组中出现的次数
        PriorityQueue<int[]>pq=new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
        //括号里是重写比较器的lambda表达式
        // part1 - part2是升序排序(小顶堆)，part2 - part1 是降序排序(大顶堆)。
        for (Map.Entry<Integer,Integer>entry:map.entrySet()){
        //通过遍历 map.entrySet() 获取每个 entry 的 key 和 value.
              if(pq.size()<k){                        //通过Map转成set就可以迭代
                  pq.add(new int[]{entry.getKey(), entry.getValue()});
             }
              else {
                  if (entry.getValue() > pq.peek()[1]) {//当前元素出现次数大于小顶堆第一个
                      pq.poll();                        //数组1下标存的是 出现频率
                      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];//数组0下标存的是 key
 
        }
        return ans;
            }
        }