239. 滑动窗口最大值 347.前 K 个高频元素

239. 滑动窗口最大值

剑指offer题目

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for(int i = 0;i < nums.length;i++){
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
                queue.removeLast();
            }
            queue.add(i);
            if(queue.peekLast() - k == queue.peek()){
                queue.poll();
            }
            if(i + 1 >= k){
                res[index++] = nums[queue.peek()];
            }
        }
        return res;
    }
}

347.前 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<int[]> queue = new PriorityQueue<>((p1,p2) -> p2[1] - p1[1]);
        Set<java.util.Map.Entry<Integer,Integer>> entries = map.entrySet();
        for(java.util.Map.Entry<Integer,Integer> entry:entries){
            int[] res = new int[2];
            res[0] = entry.getKey();
            res[1] = entry.getValue();
            queue.offer(res);
        }
        int[] result = new int[k];
        for(int i = 0;i < k;i++){
            int[] temp = queue.poll();
            result[i] = temp[0];
        }
        return result;
    }
}