前言

第一次遇见这种数据结构，记录一下。

比如：滑动窗口和高频元素，这两个题我觉得都挺接地气。

滑动窗口这题主要是获取每个窗口中的最大数并记录，和时序有关。

高频元素就像是 top-k或者 tfidf，都有其实用场景。

实现

单调递减队列

单调队列有着巧妙的插入方式。

  • 插入： 如果插入的比末尾数大，就向前清理，维护递减序列
  • 弹出： 如果弹出的是头部数（也就是最大的那个），就正常弹出，其他的忽略

由于维护了有序性，所以弹出的时候不可能出现弹出数比当前数更大的情况，其他的都被最大的那个删掉了，所以其他的可以忽略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MyQueue{
    Deque<Integer> deque = new LinkedList<>();

    /**
     * 如果删除的是头部数，弹出，其他的不用管
     */
    void poll(int num){
        if(!deque.isEmpty() && num == deque.peek()){
            deque.poll();
        }
    }

    /**
     * 如果插入的比末尾数大，向前清理，维护递减
     */
    void push(int num){
        while(!deque.isEmpty() && num > deque.getLast()){
            deque.removeLast();
        }
        deque.add(num);
    }

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

优先级队列（维护前 k 个最大的）

  • 插入： 如果插入的比队列中最小的大，弹出小的，插入这个
1
2
3
4
5
6
7
8
9
10
11
12
13
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{
        // 如果插入的比队列中最小的大，弹出小的，插入这个
        if(entry.getValue() > pq.peek()[1]){
            pq.poll();
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
    }
}