Leetcode 2503. Maximum Number of Points From Grid Queries

[Woodyiiiiiii]

这道题我一开始用BFS和DFS都试过了，显然常规不加优化的这两个方法都会TLE(BFS时间复杂度更低)。

那么要对BFS进行优化。观察题目，显然发现有重复计算的部分——query数组。

第一种方法：
对query数组进行从小到大排序，每次都记录下次BFS的位置，以此循环。同时注意排序query用TreeMap而不是用Array.sort排序，不然过不了。

还要注意的是两个队列queue和nextQueue如何在BFS每次循环中交互。

class Solution {

    final int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int[] maxPoints(int[][] grid, int[] queries) {
        int[] ans = new int[queries.length];
        int m = grid.length, n = grid[0].length;
        TreeMap<Integer, Integer> queryToCount = new TreeMap<>();
        for (int q : queries) {
            queryToCount.put(q, 0);
        }

        boolean[][] visited = new boolean[m][n];
        int sum = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        Queue<int[]> nextQueue = new LinkedList<>();

        for (int limit : queryToCount.keySet()) {
            if (grid[0][0] >= limit) {
                queryToCount.put(limit, 0);
                continue;
            }

            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int x = cur[0], y = cur[1];
                if (grid[x][y] >= limit) {
                    nextQueue.offer(cur);
                    continue;
                }
                sum++;
                visited[x][y] = true;
                for (int[] dir : dirs) {
                    int nx = x + dir[0], ny = y + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        if (grid[nx][ny] < limit) {
                            queue.offer(new int[]{nx, ny});
                        } else {
                            nextQueue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
            queryToCount.put(limit, sum);
            queue = nextQueue;
            nextQueue = new LinkedList<>();
        }

        for (int i = 0; i < queries.length; i++) {
            ans[i] = queryToCount.get(queries[i]);
        }

        return ans;
    }
    
}

第二种方法：
有没有可能绕过query数组呢，它是阻拦时间复杂度的万恶之源。

既然对二维数组用前缀和的思想，那对query数组岂不是也可以？最后再用DP(presum)的思想计算满足query的个数。这个方法绕过了query数组的循环限制。@jyy的做法

有点类似于位运算的累加了。

class Solution {

    final int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int[] maxPoints(int[][] grid, int[] queries) {
        int r = grid.length;
        int c = grid[0].length;
        int[] treeArr = new int[Arrays.stream(queries).max().getAsInt() + 1];
        int[][] maxVal = new int[r][c];
        int[][] dis = new int[][]{
                {1, 0}, {-1, 0}, {0, 1}, {0, -1}
        };
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 0});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int curMax = Math.max(grid[poll[0]][poll[1]], poll[2]);
            if (maxVal[poll[0]][poll[1]] != 0 && curMax >= maxVal[poll[0]][poll[1]]) {
                continue;
            }
            maxVal[poll[0]][poll[1]] = curMax;
            if (curMax >= treeArr.length) {
                // 没必要扩展了
                continue;
            }
            for (int[] di : dis) {
                int ii = poll[0] + di[0];
                int jj = poll[1] + di[1];
                if (ii >= 0 && ii < r && jj >= 0 && jj < c && (maxVal[ii][jj] == 0 || curMax < maxVal[ii][jj])) {
                    queue.add(new int[]{ii, jj, curMax});
                }
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (maxVal[i][j] < treeArr.length && maxVal[i][j] != 0) {
                    treeArr[maxVal[i][j]]++;
                }
            }
        }
        for (int i = 1; i < treeArr.length; i++) {
            treeArr[i] += treeArr[i - 1];
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            res[i] = treeArr[queries[i] - 1];
        }
        return res;
    }
    
}

---

• https://leetcode.com/problems/maximum-number-of-points-from-grid-queries/description/
• https://leetcode.com/problems/maximum-number-of-points-from-grid-queries/solutions/2899384/java-bfs-o-min-m-n-klogk/