LC2146. 价格范围内最高排名的 K 样物品

总体方法->BFS+堆

维度优先级：1.最短距离；2.低价格；3.小的x；4.小的y

因此只有在相同的最短路径基础上再考虑余下的3个维度，最短路我们可以通过BFS去维护

而余下的三个维度我们具体要取哪一个可以定义在堆的排序规则上，堆会将满足条件的首个元素优先弹出

题目数据范围：1 <= m, n <= 10^5，1 <= m * n <= 10^5，显然只能接收到O(NlogN)或以下级别

坑点分析：要注意不能只用一个堆，因为堆与普通的单向队列不同，堆里的元素顺序会随着新元素的插入而改变，若只用一个堆且弹出固定size数目的元素，很有可能会把这轮进来的元素也弹出来（只要这个元素足够优先）

时间复杂度:O(M*N*log(M*N)) 空间复杂度:O(M*N)

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
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        List<List<Integer>> res = new ArrayList<>();
        int m = grid.length, n = grid[0].length;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean[][] vis = new boolean[m][n];
        // 自定义规则堆:pq1存储上一轮循环的pq2遗留的元素，pq2是用来装本轮循环新的元素
        PriorityQueue<int[]> pq2 = new PriorityQueue<>((a, b) -> grid[a[0]][a[1]] == grid[b[0]][b[1]] ?
                (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]) : grid[a[0]][a[1]] - grid[b[0]][b[1]]), pq1;
        pq2.add(start);
        vis[start[0]][start[1]] = true;
        // 开启BFS
        while (!pq2.isEmpty() && res.size() < k) {
            pq1 = new PriorityQueue<>(pq2); // pq1复制上一轮的pq2且排序规则也一致
            pq2.clear();    // pq2清空，准备装新一轮的
            int size = pq1.size();
            while (size-- > 0) {
                int[] poll = pq1.poll();
                int x = poll[0], y = poll[1];
                if (grid[x][y] >= pricing[0] && grid[x][y] <= pricing[1]) {
                    res.add(Arrays.asList(x, y));   // 是商品且价钱合适
                }
                if (res.size() >= k) break; // 买够了
                // 寻找上下左右的
                for (int[] dir : dirs) {
                    int newX = x + dir[0], newY = y + dir[1];
                    // 下一个在范围内&&没有背访问过&&不是墙
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && !vis[newX][newY] && grid[newX][newY] != 0) {
                        pq2.add(new int[]{newX, newY});  // 新的位置入堆
                        vis[newX][newY] = true; // 标记访问
                    }
                }
            }
        }
        return res;
    }
}

LC6197. 最长上传前缀

懒堆的应用：

  1. 要求最长上升前缀等价于求最小未上传索引再减去1
  2. 我们可以用一个数据结构维护未上传的索引，并能及时更新这些未上传的索引以及以低的时间复杂度弹出最小未上传索引
  3. 考虑到堆remove()方法时间复杂度是O(N)，因此我们需要另外一个数据结构记录当前哪些视频已经上传，哪些还没有上传的，可以用一个boolean数组维护
  4. 当我们要求最小未上传索引时，先弹出堆顶已经上传的视频索引，那些肯定是过时数据，然后最后再弹出真正未上传的，直接计算得到结果
  5. 时间复杂度:O(NlogN)，空间复杂度:O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class LUPrefix {
    PriorityQueue<Integer> pq = new PriorityQueue<>();  // 维护未上传视频索引
    boolean[] up;   // up[video]标记有没有上传video

    public LUPrefix(int n) {
        // 注意到n+1
        for (int i = 1; i <= n + 1; i++) {
            pq.add(i);
        }
        up = new boolean[n + 2];
    }

    public void upload(int video) {
        up[video] = true;
    }

    public int longest() {
        // 先弹出堆中已经上传的视频索引
        while (!pq.isEmpty() && up[pq.peek()]) pq.poll();
        // 再查看未上传的最小视频索引，减去1就是最长上传序列
        return pq.peek() - 1;
    }
}

如果要考虑到这种求xx最小的题目，还要做到实时维护和低的时间复杂度，可以考虑懒堆结合数组的方式记录

2034. 股票价格波动

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class StockPrice {

    /*
    TreeMap+懒堆
    1.TreeMap维护最新的价格与时间戳映射，现在关键问题就是要怎样找出的单点修改下的的最值
    2.我们可以利用map映射的实时性与懒堆进行结合，具体地我们可以维护两个堆，一个大顶堆和一个小顶堆
    3.每当更新信息我们都将[时间戳,价格]的信息入队，当且仅当在查询时候我们依照map的信息排除堆中的过时信息，从而保证堆顶的弹出的是最值元素
    这种方式可以实现不用每次更新都大费周章地删除堆元素:O(N)操作
    时间复杂度:O(NlogN) 空间复杂度:O(N)
     */

    // 按照时间戳降序排序
    TreeMap<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
    // [时间戳,价格] 大顶堆与小顶堆
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

    public StockPrice() {

    }

    public void update(int timestamp, int price) {
        // 更新的信息入堆
        maxHeap.add(new int[]{timestamp, price});
        minHeap.add(new int[]{timestamp, price});
        // 更新map
        map.put(timestamp, price);
    }

    public int current() {
        return map.get(map.firstKey());
    }

    public int maximum() {
        // 先更新堆，确保堆顶的数据是最新的
        while (!maxHeap.isEmpty() && maxHeap.peek()[1] != map.get(maxHeap.peek()[0])) maxHeap.poll();
        return maxHeap.peek()[1];
    }

    public int minimum() {
        while (!minHeap.isEmpty() && minHeap.peek()[1] != map.get(minHeap.peek()[0])) minHeap.poll();
        return minHeap.peek()[1];
    }
}

总的来说，懒堆的精髓就是尽量避免主动移除O(N)操作，等到要弹出的时候再核查去掉不符合要求的数据。