栈与队列（下）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        Deque myDeque = new LinkedList<>();
        int id = 0;
        for(int i=0;i=k-1){
                res[id++] = nums[myDeque.peek()];
            }
        }

        return res;
    }
}

使用双端队列实现单调队列。遍历开始，每一次遍历都需要入队当前元素，当当前元素大于队尾元素时，队尾元素出队，且要注意k的范围，队列中始终只能维持最多k个元素，多了就要出队，为了判定窗口范围，这里压入队列的元素为index。

java中的优先队列

class Solution {
//主流做法
    public int[] topKFrequent(int[] nums, int k) {
    //统计各元素出现次数
        HashMap hm = new HashMap<>();
        for(int i=0;i> Que = new PriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue());
        Set> entries = hm.entrySet();
        for(Map.Entry entry:entries){
            Que.offer(entry);
            if(Que.size()>k){
                Que.poll();
            }
        }
        int[] res = new int[k];
        for(int i=k-1;i>=0;i--){
            res[i] = Que.poll().getKey();
        }
        return res;
    }
}

非主流做法，leetcode中官方解下，热评第一

// 借助 HashMap 数据结构
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];    // 结果数组
        Map map = new HashMap();
        // 统计数组中各元素出现的次数
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else{
                map.put(num, 1);
            }
        }

        int maxTimes = 0;    // 出现最多的元素的出现次数
        // 找出出现次数最多的元素出现的次数
        for(Map.Entry entry : map.entrySet()){
            if(entry.getValue() > maxTimes){
                maxTimes = entry.getValue();
            }
        }

        // 按出现次数从大到小添加到结果数组
        while(k > 0){
            for(Map.Entry entry : map.entrySet()){
                if(entry.getValue() == maxTimes){
                    res[k - 1] = entry.getKey();
                    k--;
                }
            }
            maxTimes--;
        }

        return res;
    }