水位上升的泳池中游泳

发表于
本文字数： 8.5k 阅读时长 ≈ 8 分钟

LeetCode每日一题，778. Swim in Rising Water

先看题目描述

yFrgw6.png

大意就是给定一个 grid，grid[i][j] 代表该位置的高度，水位会随着时间上升，时间 t 时水位为 t，若我们想从一个位置游到某相邻位置，只有当水位 t 不低于当前位置和相邻位置的高度才可以，我们可以瞬间移动无限距离，问想从左上角游到右下角，最低的水位是多少

算法和思路

这题实际上和昨天的题 最小体力消耗路径 是一样的，也是要把这个二维矩阵给抽象成图，只是对边的长度的计算方式不同，昨天的题和今天的题本质是一样的，昨天的题有三种算法可以解决，今天的题也同样

二分查找

可以使用二分查找定位到最短等待时间。具体来说：由于题目限制了 grid[i][j] 的范围，所以可以在区间 [0, N * N - 1] 里猜一个整数，针对这个整数从起点（左上角）开始做一次深度优先遍历或者广度优先遍历

  • 当小于等于该数值时，如果存在一条从左上角到右下角的路径，说明答案可能是这个数值，也可能更小；
  • 当小于等于该数值时，如果不存在一条从左上角到右下角的路径，说明答案一定比这个数值更大。

按照这种方式不断缩小搜索的区间，最终找到最少等待时间

并查集

我们可以将这 N * N 个节点放入并查集中，实时维护它们的连通性

对于 grid[i][j] 和其相邻方格 grid[i][j + 1]，我们认为其之间存在一条边，长度为 max{grid[i][j]，grid[i][j + 1]}，对于其他相邻方格也均是类似处理。因此我们可以将所有边按照长度进行升序排列，然后依次将边添加入并查集中，并将该边的两顶点所属连通分量合并，每次判断左上角和右下角是否连通，若一旦连通，那么刚刚添加的边的长度就是我们要找的答案

*Dijkstra算法 *

注意这个问题求的是从一个源点到目标顶点的最短路径，并且这条路径上的边没有负数（这一点非常重要，单元格的高度大于等于 0），符合 Dijkstra 算法的应用场景。为此我们可以把问题抽象成一个带权有向图，权值是有向边指向的顶点的高度

算法源码

二分查找

这题使用二分查找的效率是最高的，因为题目限定了 grid[i][j] 的值范围为 [0，N * N - 1]，这样二分查找的初始范围就比较小，运行时间比较短，而昨天的题里面，二分查找的初始范围比较大，运行时间比较长，效率相对来说就低些

下面是题解的 二分查找 + DFS 的代码

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
public class Solution {

    private int N;

    public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int swimInWater(int[][] grid) {
        this.N = grid.length;

        int left = 0;
        int right = N * N - 1;
        while (left < right) {
            // left + right 不会溢出
            int mid = (left + right) / 2;
            boolean[][] visited = new boolean[N][N];
            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 == N - 1 && newY == N - 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 < N && y >= 0 && y < N;
    }
}

下面是题解的 二分查找 + BFS 的代码

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
public class Solution {

    private int N;

    public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int swimInWater(int[][] grid) {
        this.N = grid.length;

        int left = 0;
        int right = N * N - 1;
        while (left < right) {
            int mid = (left + right) / 2;

            if (grid[0][0] <= mid && bfs(grid, mid)) {
                // mid 可以，尝试 mid 小一点是不是也可以呢？// [left, mid]
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }


    /**
     * 使用广度优先遍历得到从 (x, y) 开始向四个方向的所有小于等于 threshold 且与 (x, y) 连通的结点
     *
     * @param grid
     * @param threshold
     * @return
     */
    private boolean bfs(int[][] grid, int threshold) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[N][N];
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] front = queue.poll();
            int x = front[0];
            int y = front[1];
            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 == N - 1 && newY == N - 1) {
                        return true;
                    }

                    queue.offer(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }
        return false;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }

}

并查集

这题我第一反应就是使用并查集，基本就是套用的昨天写的并查集算法的代码的模板，下面是自己实现的代码

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
class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int size = n * n;
        int tar = size - 1;
        int[] parent = new int[size];
        PriorityQueue<Edge> prior = new PriorityQueue<>((a, b) -> a.len - b.len);
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int index = i * n + j;
                if (i < n - 1) {
                    prior.add(new Edge(index, index + n, Math.max(grid[i][j], grid[i + 1][j])));
                }
                if (j < n - 1) {
                    prior.add(new Edge(index, index + 1, Math.max(grid[i][j], grid[i][j + 1])));
                }
            }
        }
        while (!prior.isEmpty()) {
            Edge edge = prior.poll();
            union(edge.x, edge.y, parent);
            if (find(0, parent) == find(tar, parent)) {
                return edge.len;
            }
        }
        return 0;
    }

    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }

    private void union(int a, int b, int[] parent) {
        int x = find(a, parent);
        int y = find(b, parent);
        parent[y] = x;
    }

    private class Edge {
        int x;
        int y;
        int len;

        Edge(int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    }
}

Dijkstra 算法

下面是题解的 Dijkstra 算法的代码，里面使用到了最小堆，用于每次迭代时寻找 距离向量最小的未访问节点

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
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;
    }
}