LC-2503.矩阵查询可获得的最大分数

题目描述

leetcode 困难题

给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。
否则，你不能获得任何分，并且结束这一过程。
在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 answer 。

示例1：

输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
输出：[5,8,1]
解释：上图展示了每个查询中访问并获得分数的单元格。

提示1：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 10^5
k == queries.length
1 <= k <= 10^4
1 <= grid[i][j], queries[i] <= 10^6

优先队列 + 离线询问

由于每次询问的起点一样，显然可以得到如果 $queries[i] <= queries[j]$ ，那么前者能移动到的点必然是后者的一个子集，很容易想到从小到大进行询问。

我们可以先对询问进行排序，从小到大遍历 $queries$ 以进行离线查询。离线查询的含义为题目一次性给出了所有询问，但是我们不按照题目顺序而是以某种特定顺序进行处理。例如在该解法中，我们无法按照给出的顺序进行处理，必须按照从小到大的顺序处理询问。

具体询问过程为：通过最小堆维护当前能移动到的最小点，如果小于当前询问值，则分数加一，否则的话说明不存在任何能够移动到的新点，所以进行下次询问，如前面所说，后面询问能移动到的点肯定包含了之前询问的点，所以我们只需要在之前询问的基础上尝试移动即可。

class Solution {
    int[][] help = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    int[] fa;
    int[] size;

    public int[] maxPoints(int[][] grid, int[] queries) {
        int n = grid.length, m = grid[0].length;
        // 询问排序
        int[] qIndexSort = IntStream.range(0, queries.length).boxed()
                                .sorted((a, b) -> queries[a] - queries[b])
                                .mapToInt(Integer::valueOf)
                                .toArray();
        // 离线询问
        int[] ans = new int[queries.length];
        int count = 0;
        PriorityQueue<int[]> min = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        min.offer(new int[]{grid[0][0], 0, 0});
        grid[0][0] = 0; // visit
        for(int index : qIndexSort){
            while(!min.isEmpty() && min.peek()[0] < queries[index]){
                int[] top = min.poll();
                int a = top[1], b = top[2];
                for(int[] item : help){
                    int newA = a + item[0], newB = b + item[1];
                    if(check(newA, newB, n, m) && grid[newA][newB] > 0){
                        min.offer(new int[]{grid[newA][newB], newA, newB});
                        grid[newA][newB] = 0;
                    }
                }
                count++;
            }
            ans[index] = count;
        }
        return ans;
    }

    private boolean check(int x, int y, int m, int n){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

并查集 + 离线询问

另一种思路是使用并查集，初始化为矩阵中每个元素独立存在，然后类似前一种解法先将矩阵元素、询问分别排序后进行离线询问。

定义指针 $j$ ，初始时指向矩阵中最小的元素，然后从小到大遍历询问，如果 $gSort[j]$ 以及 $4$ 个方向上的元素满足当前询问值，则将其与 $gSort[j]$ 连通，并使 $j + 1$ ，显然每轮询问结果为 $size[find(0)]$。

class Solution {
    int[][] help = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    int[] fa;
    int[] size;

    public int[] maxPoints(int[][] grid, int[] queries) {
        int n = grid.length, m = grid[0].length, mn = n * m;
        fa = IntStream.range(0, mn).toArray();
        size = IntStream.generate(() -> 1).limit(mn).toArray();
        // 矩阵元素排序，第二维用来记录原始坐标
        int[][] gSort = new int[mn][3];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                gSort[i * m + j] = new int[]{grid[i][j], i, j};
            }
        }
        Arrays.sort(gSort, (a, b) -> a[0] - b[0]);
        // 询问排序
        int[] qIndexSort = IntStream.range(0, queries.length).boxed()
                                .sorted((a, b) -> queries[a] - queries[b])
                                .mapToInt(Integer::valueOf)
                                .toArray();
        // 矩阵遍历指针
        int j = 0;
        int[] ans = new int[queries.length];
        for(int index : qIndexSort){
            while(j < mn && gSort[j][0] < queries[index]){
                int a = gSort[j][1], b = gSort[j][2];
                for(int[] item : help){
                    int newA = a + item[0], newB = b + item[1];
                    if(check(newA, newB, n, m) && grid[newA][newB] < queries[index]){
                        union(a * m + b, newA * m + newB);
                    }
                }
                j++;
            }
            if(grid[0][0] < queries[index]){
               ans[index] = size[find(0)];
            }
        }
        return ans;
    }

    private void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y){
            return;
        }
        if(size[x] < size[y]){
            x = x ^ y;
            y = x ^ y;
            x = x ^ y;
        }
        fa[y] = x;
        size[x] += size[y];
    }

    private int find(int x){
        if(fa[x] != x){
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    private boolean check(int x, int y, int m, int n){
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}