在一个 N x N 的坐标方格 grid 中,每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t 时,此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的。当然,在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0,0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)?
示例 1:
输入: [[0,2],[1,3]]
输出: 3
解释:
时间为0时,你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向,因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时,你才可以游向平台 (1, 1). 因为此时的水位是 3,坐标方格中的平台没有比水位 3 更高的,所以你可以游向坐标方格中的任意位置
示例2:
输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释:
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
最终的路线用加粗进行了标记。
我们必须等到时间为 16,此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
提示:
2 <= N <= 50
grid[i][j]
是 [0, ..., N*N - 1]
的排列。由于在任意点可以往任意方向移动,所以相邻的点(四个方向)之间存在一条无向边。
边的权重 w
是指两点节点中的最大高度。
按照题意,我们需要找的是从左上角点到右下角点的最优路径,其中最优路径是指途径的边的最大权重值最小,然后返回最优路径中的最大权重值。
我们可以先遍历所有的点,将所有的边加入集合,存储的格式为数组 [a, b, w]
,代表编号为 a
的点和编号为 b
的点之间的权重为 w
(按照题意,w 为两者的最大高度)。
对集合进行排序,按照 w 进行从小到达排序。
当我们有了所有排好序的候选边集合之后,我们可以对边从前往后处理,每次加入一条边之后,使用并查集来查询左上角的点和右下角的点是否连通。
当我们的合并了某条边之后,判定左上角和右下角的点联通,那么该边的权重即是答案。
这道题和 【刷穿 LeetCode】1631. 最小体力消耗路径(中等) 几乎是完全一样的思路。
你甚至可以将那题的代码拷贝过来,改一下对于 w
的定义即可。
class Solution {
int n;
int[] p = new int[2509];
void union(int a, int b) {
p[find(a)] = p[find(b)];
}
boolean query(int a, int b) {
return find(a) == find(b);
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public int swimInWater(int[][] grid) {
n = grid.length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n ;i++) {
for (int j = 0; j < n; j++) {
int idx = getIndex(i, j);
p[idx] = idx;
if (i + 1 < n) edges.add(new int[]{idx, getIndex(i + 1, j), Math.max(grid[i][j], grid[i + 1][j])});
if (j + 1 < n) edges.add(new int[]{idx, getIndex(i, j + 1), Math.max(grid[i][j], grid[i][j + 1])});
}
}
Collections.sort(edges, (a,b)->a[2]-b[2]);
int start = getIndex(0, 0), end = getIndex(n - 1, n - 1);
for (int[] edge : edges) {
int a = edge[0], b = edge[1], w = edge[2];
union(a, b);
if (query(start, end)) return w;
}
return -1;
}
int getIndex(int i, int j) {
return i * n + j;
}
}
节点的数量为 n * n
,无向边的数量严格为 2 * n * (n - 1)
,数量级上为
。
,排序复杂度为
,遍历得到最终解复杂度为
。整体复杂度为
。
注意:假定 Collections.sort() 使用 Arrays.sort() 中的双轴快排实现。
也可以用「二分 + DFS」的解法。
DFS 和 BFS 思路类似,这里就只以 BFS 为例,为大家讲解这种「二分」思路。
题目给定了 grid[i][j]
的范围是 [0,
],所以答案必然落在此范围。
同时我们知道,假设最优解为 min
的话(恰好能到达右下角的时间)。小于 min
的时间无法到达右下角,大于 min
的时间能到达右下角。
因此在以最优解 min
为分割点的数轴上具有两段性,那么可以使用「二分」找到 min
:
注意:「二分」的本质是两段性,并非单调性。只要一段满足某个性质,另外一段不满足某个性质,就可以用「二分」。 其中 【刷穿 LeetCode】33. 搜索旋转排序数组(中等) 是一个很好的说明例子。
接着分析,假设最优解为 min
,我们在 [l, r]
范围内进行二分,当前二分到的时间为 mid
时:
min <= mid
,让 r = mid
min > mid
,让 l = mid + 1
下面给出一个可读性高(偏工程一点)的解法:
class Solution {
private final int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
public int swimInWater(int[][] grid) {
int n = grid.length;
int l = 0, r = n * n;
while (l < r) {
int mid = l + r >> 1;
if (check(grid, mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
private boolean check(int[][] grid, int time) {
int n = grid.length;
boolean[][] visited = new boolean[n][n];
Deque<int[]> queue = new ArrayDeque<>();
queue.addLast(new int[]{0, 0});
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] pos = queue.pollFirst();
int x = pos[0], y = pos[1];
if (x == n - 1 && y == n - 1) return true;
for (int[] dir : dirs) {
int newX = x + dir[0], newY = y + dir[1];
int[] to = new int[]{newX, newY};
if (inArea(n, newX, newY) && !visited[newX][newY] && canMove(grid, pos, to, time)) {
visited[newX][newY] = true;
queue.addLast(to);
}
}
}
return false;
}
private boolean inArea(int n, int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
private boolean canMove(int[][] grid, int[] from, int[] to, int time) {
return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]);
}
}
] 范围内进行二分,复杂度为
;每一次 BFS 最多有
个节点入队,复杂度为
。整体复杂度为
下面的是我第一次实现「二分 + BFS」时写的代码,应该是比较偏竞赛的实现。
为了让其变得稍微可读,我加了一点点注释和换行:
class Solution {
int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
int[][] grid;
boolean[] st;
int n;
public int swimInWater(int[][] _grid) {
grid = _grid;
n = grid.length;
int l = 0, r = n * n;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
boolean check(int t) {
// st 和 d 装的都是 (x,y) 转换出来的 idx
// 由 (x,y) 得 idx: idx = x * n + y
// 由 idx 得 (x,y): x = idx / n, y = idx % n;
st = new boolean[n * n];
Deque<Integer> d = new ArrayDeque<>();
d.addLast(0); // 等同 a.addLast(0 * n + 0);
st[0] = true; // 等同 st[0 * n + 0] = true;
int end = (n - 1) * n + (n - 1);
while (!d.isEmpty()) {
int idx = d.pollFirst();
if (idx == end) return true;
int x = idx / n, y = idx % n;
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
// 将一些赋值为 true 的表达式嵌在判断条件里的写法其实并不冷门,在 Java 不少数据结构实现中都有(ConcurrentHashMap...)
// 我这里采用这种写法的目的是为了可以少写一对大括号,同时将下面的四行代码在一行内写完。这里为了大家看着方便,我分为了四行
if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
!st[nx * n + ny] &&
t >= Math.max(grid[x][y], grid[nx][ny]) &&
(st[nx * n + ny] = true)) d.addLast(nx * n + ny);
}
}
return false;
}
}
如果采用这种写法,我大概在 5 分钟内可以保证调试通过,但是如果是上面的考虑封装性和可读性的写法,我可能需要 10 分钟都不止。
大家可能对 AC 时间的概念不太了解,对于 ACM 赛制而言,如果你某道题慢了 5 钟,带来的影响不只是总时长增加了 5 分钟,而是后面的每道题的时长都增加了 5 分钟。
因为 ACM 记录的是每道题的通过时间,然后加起来作为总时间。
比如总共 10 道题吧,正常你每道题的完成时间是 1 分钟的话,你花的总时间是 1+2+3+...+9+10=55
,但是如果你第一道题慢了 1 分钟,后面的题花费时间不变的话,你花的总时间是 2+3+4+...+10+11=65
。也就是某道题慢了带来的影响是后面的所有题都相应的慢了。
所以首先它代码更短,比赛中可以更快的 AC。
其次有着更高的效率。因为少了大量的函数调用开销(次要),以及数组创建(主要),这里说的数组主要是指存入的 stack 中的数组。
因此,如果你是竞赛生,无论是从执行效率和编码效率来说,我都推荐你从现在开始培养自己的竞赛写法。
最后,也许你不会遇到,但是需要知道的一点是,这种竞赛写法会有「并发安全问题」。
例如创建了一个 Solution
对象,在多个线程中同时调用 swimInWater
方法,会因为你使用了成员变量来保存 grid
、st
和 n
导致答案出错。但是放心 OJ 不会采用这种方式来测试你的代码。
上面考虑封装性的代码没有创建会被发生资源抢夺的成员变量,不会有「并发安全问题」。
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。