05 August 2008
在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
示例 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) 是连通的
根据题目中的描述：
如果等待的时间 t 越少，网格上可以游泳的部分就越少，存在从左上角到右下角的一条路径的可能性越小；
如果等待的时间 t 越多，网格上可以游泳的部分就越多，存在从左上角到右下角的一条路径的可能性越大。
这是本问题具有的 单调性。因此可以使用二分查找定位到最短等待时间。具体来说：在区间 [0, N * N - 1] 里猜一个整数，针对这个整数从起点（左上角）开始做一次深度优先遍历或者广度优先遍历。
当小于等于该数值时，如果存在一条从左上角到右下角的路径，说明答案可能是这个数值，也可能更小；
当小于等于该数值时，如果不存在一条从左上角到右下角的路径，说明答案一定比这个数值更大。
按照这种方式不断缩小搜索的区间，最终找到最少等待时间。
时间复杂度：O(N^2 * log N)
空间复杂度：O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
private int len;
public static final int[][] DIRECTIONS = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
public int swimInWater(int[][] grid) {
this.len = grid.length;
int left = 0;
int right = len * len - 1;
while (left < right) {
// left + right 不会溢出
int mid = (left + right) / 2;
boolean[][] visited = new boolean[len][len];
if (grid[0][0] <= mid && dfs(grid, 0, 0, visited, mid)) {
// mid 可以，尝试 mid 小一点是不是也可以呢？下一轮搜索的区间 [left, mid]
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/**
* 使用深度优先遍历得到从 (x, y) 开始向四个方向的所有小于等于 threshold 且与 (x, y) 连通的结点
*
* @param grid
* @param x
* @param y
* @param visited
* @param threshold
* @return
*/
private boolean dfs(int[][] grid, int x, int y, boolean[][] visited, int threshold) {
visited[x][y] = true;
for (int[] direction : DIRECTIONS) {
int newX = x + direction[0];
int newY = y + direction[1];
if (inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] <= threshold) {
if (newX == len - 1 && newY == len - 1) {
return true;
}
if (dfs(grid, newX, newY, visited, threshold)) {
return true;
}
}
}
return false;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < len && y >= 0 && y < len;
}
}
由于题目要找的是最少等待时间，可以模拟下雨的过程，把网格抽象成一个无权图，每经过一个时刻，就考虑此时和雨水高度相等的单元格，考虑这个单元格的上、下、左、右、四个方向，并且高度更低的单元格，把它们在并查集中进行合并。
时间复杂度：O(N^2 * log N)
空间复杂度：O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
private int len;
public static final int[][] DIRECTIONS = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
public int swimInWater(int[][] grid) {
this.len = grid.length;
int len = this.len * this.len;
// 下标：方格的高度，值：对应在方格中的坐标
int[] index = new int[len];
for (int i = 0; i < this.len; i++) {
for (int j = 0; j < this.len; j++) {
index[grid[i][j]] = getIndex(i, j);
}
}
UnionFind unionFind = new UnionFind(len);
for (int i = 0; i < len; i++) {
int x = index[i] / this.len;
int y = index[i] % this.len;
for (int[] direction : DIRECTIONS) {
int newX = x + direction[0];
int newY = y + direction[1];
if (inArea(newX, newY) && grid[newX][newY] <= i) {
unionFind.union(index[i], getIndex(newX, newY));
}
if (unionFind.isConnected(0, len - 1)) {
return i;
}
}
}
return -1;
}
private int getIndex(int x, int y) {
return x * len + y;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < len && y >= 0 && y < len;
}
private class UnionFind {
private int[] parent;
public UnionFind(int n) {
this.parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int root(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public boolean isConnected(int x, int y) {
return root(x) == root(y);
}
public void union(int p, int q) {
if (isConnected(p, q)) {
return;
}
parent[root(p)] = root(q);
}
}
}
注意这个问题求的是从一个源点到目标顶点的最短路径，并且这条路径上的边没有负数（这一点非常重要，单元格的高度大于等于 00），符合 Dijkstra 算法的应用场景。为此我们可以把问题抽象成一个带权有向图，权值是有向边指向的顶点的高度。
Dijkstra 算法是应用很广泛的求解 没有负权边 的单源最短路径算法，《算法（第 4 版）》对这个算法做了详细的介绍，大家还可以阅读这本书的配套英文教程的 4.4 Shortest Paths 进行学习。没有负权边是应用 Dijkstra 算法的前提，也是理解 Dijkstra 算法执行流程的关键。
时间复杂度：O(N^2 * log N)
空间复杂度：O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class Solution {
// Dijkstra 算法（应用前提：没有负权边，找单源最短路径）
public int swimInWater(int[][] grid) {
int n = grid.length;
Queue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> grid[o[0]][o[1]]));
minHeap.offer(new int[]{0, 0});
boolean[][] visited = new boolean[n][n];
// distTo[i][j] 表示：到顶点 [i, j] 须要等待的最少的时间
int[][] distTo = new int[n][n];
for (int[] row : distTo) {
Arrays.fill(row, n * n);
}
distTo[0][0] = grid[0][0];
int[][] directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
while (!minHeap.isEmpty()) {
// 找最短的边
int[] front = minHeap.poll();
int currentX = front[0];
int currentY = front[1];
if (visited[currentX][currentY]) {
continue;
}
// 确定最短路径顶点
visited[currentX][currentY] = true;
if (currentX == n - 1 && currentY == n - 1) {
return distTo[n - 1][n - 1];
}
// 更新
for (int[] direction : directions) {
int newX = currentX + direction[0];
int newY = currentY + direction[1];
if (inArea(newX, newY, n) && !visited[newX][newY] &&
Math.max(distTo[currentX][currentY], grid[newX][newY]) < distTo[newX][newY]) {
distTo[newX][newY] = Math.max(distTo[currentX][currentY], grid[newX][newY]);
minHeap.offer(new int[]{newX, newY});
}
}
}
return -1;
}
private boolean inArea(int x, int y, int n) {
return x >= 0 && x < n && y >= 0 && y < n;
}
}