Maximum Number of Points From Grid Queries

You are given an $m \times n$ integer matrix grid and an array queries of size $k$.

Find an array answer of size $k$ such that for each integer queres[i] you start in the top left cell of the matrix and repeat the following process:

• If queries[i] is strictly greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any adjacent cell in all $4$ directions: up, down, left, and right.
• Otherwise, you do not get any points, and you end this process.

After the process, answer[i] is the maximum number of points you can get. Note that for each query you are allowed to visit the same cell multiple times.

Return the resulting array  answer.

Example 1:

Input: grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]
Output: [5,8,1]
Explanation: The diagrams above show which cells we visit to get points for each query.

Example 2:

Input: grid = [[5,2,1],[1,1,2]], queries = [3]
Output: [0]
Explanation: We can not get any points because the value of the top left cell is already greater than or equal to 3.

Constraints:

• $m ~\mathrm{==}~ \text{grid.length}$
• $n ~\mathrm{==}~ \text{grid}[i].\text{length}$
• $2 \leq m, n \leq 1000$
• $4 \leq m \times n \leq {10}^5$
• $k ~\mathrm{==}~ \text{queries.length}$
• $1 \leq k \leq {10}^4$
• $1 \leq \text{grid}[i][j], \text{queries}[i] \leq {10}^6$

解题思路

　　暴力做的话可以用并查集，遍历每一个询问，然后再遍历一遍矩阵的每个格子把值小于询问的四个方向格子进行合并，最后输出输出$(0, 0)$所在连通块的格子数目，这种做法的时间复杂度为$O(k \cdot n \cdot m)$，会超时。

　　可以发现随着查询的值逐渐增大，那么能合并的格子越多，连通块不断往外扩展而不会减少，$(0, 0)$所在连通块的格子数量也会越大。因此可以进行离线处理，把询问按照值从小到大排序，那么从小到大枚举每个询问时能用到的格子会越来越多。一开始假设矩阵一个格子都没有，从小到大枚举每个询问，把所有值小于当前询问的格子添加到矩阵中，同时往这个格子的四个方向进行合并连通块（合并值小于当前询问的格子），当无法再加入格子时当前询问的答案就是$(0, 0)$所在连通块的格子数量。

　　AC代码如下，时间复杂度为$O(nm+k)$：

 1 class Solution {
 2 public:
 3     struct Node {
 4         int val, x, y;
 5         
 6         bool operator<(Node &t) {
 7             return val < t.val;
 8         }
 9     };
10     
11     vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
12         int n = grid.size(), m = grid[0].size();
13         vector<Node> g;
14         for (int i = 0; i < n; i++) {
15             for (int j = 0; j < m; j++) {
16                 g.push_back({grid[i][j], i, j});    // 存每个格子的信息
17             }
18         }
19         sort(g.begin(), g.end());   // 按照值把格子从小到大排序
20         vector<int> fa, cnt;
21         for (int i = 0; i < n * m; i++) {
22             fa.push_back(i);
23             cnt.push_back(1);
24         }
25         vector<int> p;
26         for (int i = 0; i < queries.size(); i++) {
27             p.push_back(i);
28         }
29         sort(p.begin(), p.end(), [&](int i, int j) {    // 对询问从小到大排序
30             return queries[i] < queries[j];
31         });
32         vector<int> ans(queries.size());
33         int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
34         function<int(int)> find = [&](int x) {
35             return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
36         };
37         for (int i = 0, j = 0; i < queries.size(); i++) {
38             while (j < g.size() && g[j].val < queries[p[i]]) {  // 把所有值小于当前询问queries[p[i]]的格子添加到矩阵中
39                 int x = g[j].x, y = g[j].y; // 当前格子的坐标
40                 j++;
41                 for (int k = 0; k < 4; k++) {   // 四个方向合并
42                     int xx = x + dx[k], yy = y + dy[k];
43                     if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
44                     if (grid[xx][yy] >= queries[p[i]]) continue;    // 合并值小于当前询问的格子
45                     int a = find(x * m + y), b = find(xx * m + yy);
46                     if (a != b) {
47                         cnt[b] += cnt[a];
48                         fa[a] = b;
49                     }
50                 }
51             }
52             if (queries[p[i]] > grid[0][0]) ans[p[i]] = cnt[find(0)];   // 当前询问就是(0, 0)格子所在连通块的格子数量，同时要保证询问的值大于grid[0][0]
53         }
54         return ans;
55     }
56 };

　　当时比赛的时候写的是bfs，不过把队列换成了优先队列。也是离线处理。对于某个询问，我们要求的是从$(0, 0)$开始扩展，每次扩展的格子的值都小于当前查询，最后看看能够扩展多少个格子，因此先把$(0, 0)$压入队列，然后每次从队列弹出元素往四个方向扩展就可以实现。同样发现随着查询的值增加，能够扩展的格子越多，因此在一步步的扩展中，我们应该每次从值最小的格子进行扩展，即每次从队列弹出最小的元素，这样才能够保证对于值较小的询问从$(0, 0)$开始把能够扩展的格子先扩展完，因此要把普通队列换成优先队列。

　　每次查看堆顶元素，如果查询的值（从小到大排序）小于等于堆顶元素则表示对于该查询已无法再从该格子进行扩展（且从$(0, 0)$开始能扩展完的格子已扩展完），那么答案就是已扩展的格子数量。

　　AC代码如下，时间复杂度为$O(nm\log{nm})$：

 1 class Solution {
 2 public:
 3     struct Node {
 4         int val, x, y;
 5 
 6         bool operator<(const Node &t) const {   // 重载优先队列的<运算符，这里的<比较的是优先级
 7             // 如果a<b为true，意味着a的优先级小于b，那么a在b的下面
 8             // 如果a<b为false，意味着a的优先级大于b，那么a在b的上面
 9             // 由于这里要实现小根堆，因此应该让值小的元素在值大的元素上面
10             return val > t.val; // 如果当前的this->t > t.val，那么返回true，this在t的下面，即更大的值在下面（那么小的就在上面）
11         }
12     };
13     
14     vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) {
15         int n = grid.size(), m = grid[0].size();
16         vector<int> p;
17         for (int i = 0; i < queries.size(); i++) {
18             p.push_back(i);
19         }
20         sort(p.begin(), p.end(), [&](int i, int j) {
21             return queries[i] < queries[j];
22         });
23         priority_queue<Node> q; // 小根堆
24         q.push({grid[0][0], 0, 0});
25         vector<vector<bool>> vis(n, vector<bool>(m));
26         vis[0][0] = true;
27         vector<int> ans(queries.size(), -1);
28         int cnt = 0, idx = 0;   // cnt表示已经扩展的格子数量，idx是查询的下标
29         int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
30         while (!q.empty()) {
31             while (idx < queries.size() && queries[p[idx]] <= q.top().val) {    // 对于当前查询已无法再从堆顶的格子扩展
32                 ans[p[idx++]] = cnt;    // 答案就是已扩展格子的数量
33             }
34             int x = q.top().x, y = q.top().y;   // 弹出值最小的格子
35             q.pop();
36             cnt++;  // 已扩展格子数量加1
37             for (int i = 0; i < 4; i++) {
38                 int xx = x + dx[i], yy = y + dy[i];
39                 if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
40                 if (vis[xx][yy]) continue;
41                 vis[xx][yy] = true;
42                 q.push({grid[xx][yy], xx, yy});
43             }
44         }
45         for (auto &it : ans) {  // 最后还没遍历到的查询意味着可以扩展到所有的格子
46             if (it == -1) it = cnt;
47         }
48         return ans;
49     }
50 };

参考资料

　　力扣第323场周赛：https://www.bilibili.com/video/BV1DD4y1a7JG/