代码随想录第十三天

Posted on 2024-01-07 In 代码随想录

239 滑动窗口最大值

https://leetcode.com/problems/sliding-window-maximum/description/
在线性时间复杂度完成

经典使用单调队列的题目

难点是如何求一个区间里面的最大值

此时需要一个队列，放进窗口元素，然后随着窗口的移动，队列一进一出，每次移动之后，队列返回最大值

此队列没有必要维护窗口里的所有元素，只需要维护可能成为窗口里最大值的元素就可以，同时保证队列里的元素数值是由大到小的
维护元素单调递减或递增（这里是递减）的队列就是单调队列

如何在不维护所有元素的情况下配合窗口移动

pop() 如果窗口移除的元素value等于单调队列的出口元素，队列弹出元素，否则不用操作
push() 如果push的元素大于入口元素的数值，将队列入口弹出，指到push元素的数值小于等于队列入口元素数值为止

保持这个规则，que.front()就一直会是最大值

自定义数组，规则和上面的一样


class MyQueue{
    Deque<Integer> myqueue = new LinkedList<>();
	
	// 如果队列顶不是要退出的值，不动
    void poll(int val){
        if (!myqueue.isEmpty() && val == myqueue.peek()){
            myqueue.pollFirst();
        }
    }
	// 推入的值和之前的值比较，推入的值大，就删一个，一直删到没有或者小于原队列的值
    void add(int val){
        while (!myqueue.isEmpty() && val > myqueue.getLast()){
            myqueue.removeLast();
        }

        myqueue.add(val);
    }
	// 队列顶部一定是最大值
    int peek(){
        return myqueue.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1){
            return nums;
        }
        
        MyQueue record = new MyQueue();
        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < k; i++){
            record.add(nums[i]);
        }
        result[0] = record.peek();

        int index = 1;
        for (int i = k; i < nums.length; i++){
            record.poll(nums[i-k]);
            record.add(nums[i]);
            result[index++] = record.peek();
        }
		
        return result;
    }
}

利用双端队列手动实现单调队列
用一个单调队列存储对应下标，窗口滑动时，直接取队列的头部指针对应的值放入结果集中

因为单调队列存储的时下标，则需要满足两个条件
1. 队列的头节点需要在[i - k + 1, i]之中
2. 既然是单调，所以放进去的数字要比末尾的大，否则弹出队尾


class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> record = new ArrayDeque<>();

        int[] result = new int[nums.length - k + 1];
        int index = 0;

        for (int i = 0; i < nums.length; i++){
            while (!record.isEmpty() && record.peek() < i - k + 1){
                record.poll();
            }

            while (!record.isEmpty() && nums[record.getLast()] < nums[i]){
                record.removeLast();
            }

            record.add(i);

            if (i >= k - 1){
                result[index++] = nums[record.peek()];
            }
        }

        return result;
    }
}

前K个高频元素

https://leetcode.com/problems/top-k-frequent-elements/description/

此题分三步

统计元素出现频率
对频率排序
找出前K个高频元素

统计用map来做

终点是排序即优先级队列
优先级队列对外接口只是从队头取元素，从队尾添加元素
优先级队列内部元素是自动依照元素权值排列
堆是一颗完全二叉树，树中每个节点的值都不小于或不大于左右孩子的值
如果父亲节点大于等于左右孩子就是大顶堆
如果父亲节点小于等于左右孩子就是小顶堆

此题使用优先级队列对部分频率进行排序
因为要统计最大前K个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里累积的才是前K个最大元素

具体实现思路
先用map统计频率，之后构建小顶堆，将所有频率入到堆中，如果堆大小大于K，弹出堆顶，之后倒叙构建数组

小顶堆实现

注意代码写法
统计次数， map的getOrDefault写法

怎么利用PriorityQueue建立小顶堆

添加到小顶堆的操作

顶堆的poll()
add()

遍历map
Map.Entry<Integer,Integer> entry : map.entrySet()

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> record = new HashMap<>();

        for (int i : nums){
            record.put(i, record.getOrDefault(i, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);

        for (Map.Entry<Integer, Integer> entry: record.entrySet()){
            if (pq.size() < k){
                pq.add(new int[] {entry.getKey(), entry.getValue()});
            } else {
                if (pq.peek()[1] < entry.getValue()){
                    pq.poll();
                    pq.add(new int[] {entry.getKey(), entry.getValue()});
                }
            }
        }

        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--){
            result[i] = pq.poll()[0];
        }

        return result;
    }
}

大顶堆实现
大顶堆实现，比较暴力
把所有元素全部推入大顶堆中，有K个元素，就poll()K次得到数组

class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer,Integer> record = new HashMap<>();

        for (int i : nums){
            record.put(i, record.getOrDefault(i, 0) + 1);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);

        for (Map.Entry<Integer, Integer> entry : record.entrySet()){
            pq.add(new int[] {entry.getKey(), entry.getValue()});
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++){
            result[i] = pq.poll()[0];
        }

        return result;
        
    }
}