代码随想录三刷day16

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。 使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。

一、力扣239. 滑动窗口最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deq = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i ++){
            if(!deq.isEmpty() && deq.peekFirst() <= i-k){
                deq.pollFirst();
            }
            if(deq.isEmpty()){
                deq.offerLast(i);
            }else{
                while(!deq.isEmpty() && nums[deq.peekLast()] < nums[i]){
                    deq.pollLast();
                }
                deq.offerLast(i);
            }
            if(i >= k -1){
                res.add(nums[deq.peekFirst()]);
            }
        }
        int[] array = res.stream().mapToInt(Integer::intValue).toArray();
        return array;
    }
}

二、力扣347. 前 K 个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>(
            (a,b)->b.getValue()-a.getValue());
            Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i ++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        for(Map.Entry<Integer,Integer> m : map.entrySet()){
            pq.offer(m);
        }
        int[] res = new int[k];
        for(int i = 0; i < k; i ++){
            Map.Entry<Integer,Integer> e = pq.poll();
            res[i] = e.getKey();
        }
        return res;
    }
}