滑动窗口最大值

题目链接

https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

思路

单调递增或者递减队列的场景，自己维护队列，每次滑动窗口时进行更新

    public int[] maxSlidingWindow(int[] nums, int k) {
    MyQueue myQueue = new MyQueue();
    int[] res = new int[nums.length - k + 1];
    for(int i = 0; i< k;i++) {
        myQueue.add(nums[i]);
    }
    int num = 0;
    res[num++] = myQueue.peek();
    for(int i =k;i<nums.length;i++) {
        myQueue.poll(nums[i - k]);
        myQueue.add(nums[i]);
        res[num++] = myQueue.peek();
    }
    return res;
}
  }

    class MyQueue {
private Deque<Integer> deque = new LinkedList();


public void poll(int val) {
    if(!deque.isEmpty() && deque.peek() == val) {
        deque.poll();
    }
}

public void add(int val) {
    while(!deque.isEmpty() && deque.getLast() < val) {
        deque.removeLast();
    }
    deque.add(val);
}

public int peek() {
    return deque.peek();
}
}

前K个高频元素

题目链接

https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

思路

topk问题，用堆解决

    public int[] topKFrequent(int[] nums, int k) {
        // 优先级队列，为了避免复杂 api 操作，pq 存储数组
        // lambda 表达式设置优先级队列从大到小存储 o1 - o2 为从大到小，o2 - o1 反之
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] res = new int[k]; // 答案数组为 k 个元素
        Map<Integer, Integer> map = new HashMap<>(); // 记录元素出现次数
        for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        for(Map.Entry<Integer,Integer> x : map.entrySet()) { // entrySet 获取 k-v Set 集合
            // 将 kv 转化成数组
            int[] tmp = new int[2];
            tmp[0] = x.getKey();
            tmp[1] = x.getValue();
            pq.offer(tmp);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        for(int i = 0; i < k; i ++) {
            res[i] = pq.poll()[0]; // 获取优先队列里的元素
        }
        return res;
    }