[刷题记录Day13]Leetcode

番茄随想 / 2023-08-26 / 原文

No.1

题目

滑动窗口最大值

思路

编写单调队列类
讲解

代码

class MonoQue {  
    Deque<Integer> deque = new LinkedList<>();  
  
    // 弹出元素时，比较当前要弹出的值是否等于队列出口的值，相等则弹出  
    // 同时判断队列此时是否为空  
    void poll(int val) {  
        if (!deque.isEmpty() && deque.peek() == val)  
            deque.poll();  
    }  
  
    // 添加元素时，如果要添加的元素大于入口处的元素，则将入口元素弹出  
    // 保证队列单调递减  
    void add(int val) {  
        while (!deque.isEmpty() && val > deque.getLast())  
            deque.removeLast();  
        deque.add(val);  
    }  
  
    // 队列出口元素始终为最大值  
    int peek() {  
        return deque.peek();  
    }  
}  
  
public int[] maxSlidingWindow(int[] nums, int k) {  
    MonoQue monoQue = new MonoQue();  
    int[] res = new int[nums.length - k + 1];  
  
    for (int i = 0; i < k; i++) {  
        monoQue.add(nums[i]);  
    }  
    int left = 0, right = k, index = 0;  
    // 初始化，取出最大值  
    res[index++] = monoQue.peek();  
    while (right < nums.length) {  
        monoQue.poll(nums[left++]);  
        monoQue.add(nums[right++]);  
        res[index++] = monoQue.peek();  
    }  
  
    return res;  
}

No.2

题目

前 K 个高频元素

思路

优先队列，小顶堆
队列poll的只剩下前K个高频元素

代码

public int[] topKFrequent(int[] nums, int k) {  
    int[] result = new int[k];  
    // (number, frequency)  
    Map<Integer, Integer> map = new HashMap<>();  
    // 统计频率  
    for (int item : nums)  
        map.put(item, map.getOrDefault(item, 0) + 1);  
  
    PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);  
    for (Map.Entry<Integer, Integer> entry: map.entrySet()) {  
        if (pq.size() < k) {  
            pq.add(new int[]{entry.getKey(), entry.getValue()});  
        } else { // pq.size() >= k  
            // 只有当前频率大于小顶堆频率时才弹出，考虑以下例子：  
            // k=2, 频率数组=[3,2,1]  
            // 不能为了1，把3弹出  
            if (entry.getValue() > pq.peek()[1]) {  
                pq.poll();  
                pq.add(new int[]{entry.getKey(), entry.getValue()});  
            }  
        }  
    }  
  
    int index = 0;  
    while (pq.size() > 0)  
        result[index++] = pq.poll()[0];  
  
    return result;  
}