这道题可以用优先队列BFS 排序 离线查询的思路解决。核心思路· 对于每个查询 q我们需要找出所有值小于 q 的单元格并统计从 (0,0) 出发能到达多少个。· 因为查询可能有重复、顺序无关可以将 queries 排序从小到大处理这样就能利用之前的结果。· 用一个最小堆来按网格值从小到大的顺序扩展可达区域。算法步骤1. 将 queries 转成带索引的数组按值排序。2. 用最小堆 (grid[r][c], r, c) 存储当前边界初始放入 (grid[0][0], 0, 0)。3. 用一个 visited 布尔数组记录是否已访问。4. 对排序后的每个查询值 (q, idx)· 从堆中弹出所有值 q 的格子每弹出一个计数 1并向四个方向扩展如果邻格未访问且其值也小于 q直接扩展否则其值大于等于 q则不能立刻加入堆作为扩展这里要注意逻辑· 更准确地说堆里存放的是当前已知可访问区域的边界。弹出时只弹出值 q 的边界点然后把它的四个邻居加入堆无论值多少因为将来 q 变大时可能被访问但邻居如果值 q 要继续处理吗需要循环直到堆顶值 ≥ q。详细BFS过程· 堆里存放元素 (val, r, c)。· 对每个查询 q1. 只要堆非空且堆顶的 val q· 弹出 (val, r, c)count· 对四个方向 (nr, nc)· 未越界且未访问· 标记访问· 入堆 (grid[nr][nc], nr, nc)2. 记录该查询答案为 count这样所有查询处理完后即可得到结果。时间复杂度· 每个格子最多入堆一次O(mn log(mn))· 查询排序O(k log k)· 总复杂度O(mn log(mn) k log k)代码实现javapublic int[] maxPoints(int[][] grid, int[] queries) {int m grid.length, n grid[0].length;int k queries.length;int[][] qs new int[k][2];for (int i 0; i k; i) {qs[i][0] queries[i];qs[i][1] i;}Arrays.sort(qs, (a, b) - a[0] - b[0]);// 最小堆: (grid[r][c], r, c)PriorityQueueint[] pq new PriorityQueue((a, b) - a[0] - b[0]);boolean[][] visited new boolean[m][n];visited[0][0] true;pq.offer(new int[]{grid[0][0], 0, 0});int[] res new int[k];int count 0;int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}};for (int[] q : qs) {int val q[0], idx q[1];while (!pq.isEmpty() pq.peek()[0] val) {int[] cur pq.poll();count;int r cur[1], c cur[2];for (int[] d : dirs) {int nr r d[0];int nc c d[1];if (nr 0 nr m nc 0 nc n !visited[nr][nc]) {visited[nr][nc] true;pq.offer(new int[]{grid[nr][nc], nr, nc});}}}res[idx] count;}return res;}示例验证以 grid [[1,2,3],[2,5,7],[3,5,1]], queries [5,6,1] 为例· 排序后 queries: [1,5,6]· 对 q1: 只能访问 (0,0) 值为1 → count1· 对 q5: 堆顶 25访问 (0,1) 值为2 → count2堆顶 35访问 (0,2) 值为3 → count3堆顶 35访问 (1,0) 值为2 → count4堆顶 5≥5 停止 → 答案 count4· 对 q6: 继续扩展最终 count7这样每个查询都得到了正确答案。
