代码随想录算法训练营第13天

class MyDequeue {
    // 双向队列，队尾存储最小值，队首存储最大值
    Deque<Integer> queue = new LinkedList<Integer>();
 
    // 窗口滑动，要移出元素时，比较当前要弹出的数值是否等于队尾的数值，如果相等则弹出
    public void poll(int val) {
        if(!queue.isEmpty() && val == queue.peek()) {
            queue.poll();
        }
    }
 
    // 窗口滑动，要加入元素时，从后往前移除比这个元素小的队列元素
    // 保证了:  1.队列元素从头到尾递增；
    //          2.比这个元素资历深但小的元素都被移除（这些元素以后永远不会是窗口最大值了）；
    //          3.移出元素时，由于(2.)，可以保证弹出队首元素（记为a）后的下一个元素（记为b）一定还在窗口内，否则a加入的时候b就已经被移除了。
    public void offer(int val) {
        while(!queue.isEmpty() && val > queue.peekLast()) {
            queue.pollLast();
        }
        queue.offer(val);
    }
 
    // 队首元素始终为最大值
    public int peek() {
        return queue.peek();
    }
}
 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) return nums;
        int[] res = new int[nums.length - k + 1];
        int res_num = 0;
        MyDequeue queue = new MyDequeue();
        // 先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        res[res_num++] = queue.peek();
        for(int i = k; i < nums.length; i++) {
            queue.offer(nums[i]);
            queue.poll(nums[i - k]);
            res[res_num++] = queue.peek();
        }
        return res;
    }
}

// 自定义类，实现Comparable接口，重写compareTo方法
class MyCount implements Comparable<MyCount>{
    public int key;
    public int value;
    public MyCount(int key, int value) {
        this.key = key;
        this.value = value;
    }
    public int getKey() {return this.key;}
    public int getValue() {return this.value;}
    public int compareTo(MyCount x) {
        // 这里的“等于返回1”，保证了相同value的元素不会被覆盖
        if(x.getValue() >= this.value) return 1;
        else return -1;
    }
}
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // hashmap统计元素出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) map.put(nums[i], map.get(nums[i]) + 1);
            else map.put(nums[i], 1);
        }
        
        // treeset排序
        Set<MyCount> tree = new TreeSet<>();
        // 此for复杂度O(n)
        for(Map.Entry<Integer, Integer> e : map.entrySet()) {
            // 此步复杂度O(logn)
            tree.add(new MyCount(e.getKey(), e.getValue()));
        }
 
        // 取tree中前k
        int[] ans = new int[k];
        int i = 0;
        for(MyCount e : tree) {
            ans[i++] = e.getKey();
            if(i == k) break;
        }
        return ans;
    }
}

/*Comparator接口说明:
 * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
 * 对于队列：排在前面意味着往队头靠
 * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
 *                                从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
 * */
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // hashmap统计元素出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) map.put(nums[i], map.get(nums[i]) + 1);
            else map.put(nums[i], 1);
        }
        // （优先队列实现的）小堆来找前k大
        // 小堆存储上述map的键值对
        PriorityQueue<int[]> pq = new PriorityQueue<>((e1, e2) -> e1[1] - e2[1]);
        // 此for复杂度O(n)
        for(Map.Entry<Integer, Integer> e:map.entrySet()) {
            // 先放k个
            if(pq.size() < k) pq.offer(new int[]{e.getKey(), e.getValue()});
            else {
                // 若当前根小于e.getValue()，则剔除根，加入e
                // 此步复杂度O(logk)
                if(e.getValue() > pq.peek()[1]) {
                    pq.poll();
                    pq.offer(new int[]{e.getKey(), e.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for(int i = 0; i < k; i++) ans[i] = pq.poll()[0];
        return ans;
    }
}