Leetcode 2503. Maximum Number of Points From Grid Queries #162
Description
这道题我一开始用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;
}
}