778. Swim in Rising Water

Leetcode link

解题思路

这道题有两个解决思路，一个是用 DFS+binary search；一个是用 dijkstra + priority queue

DFS+binary search

题目要求我们从左上角游到右下角，并且要求路线上最高的那个点最小的路线

从点 A 到点 B 的路线我们可以用 dfs 来搜索，但是 dfs 在找到点 B 之前无法判断当前路径是否是最优路径

所以我们可以用 grid[i][j] 这个因素来限制 dfs，其范围是：0 <= grid[i][j] < n^2

所以我们可以用二分法来缩小 dfs 找到最优路径的范围

步骤如下：

1. 首先划定答案范围：max(grid[0][0], grid[n - 1][n - 1]) ～ n*n - 1，其中 n === grid.length === grid[0].length
2. 取得范围的中间值 mid，然后从 grid[0][0] 开始进行 dfs
3. 一旦 dfs 过程中发现所需时间大于 mid，则终止 dfs，并且将范围改为 mid ～ n*n-1
4. 如果该 dfs 成功到达了 grid[n - 1][n - 1]，则将范围改为 max(grid[0][0], grid[n - 1][n - 1]) ～ mid
5. 不断缩小范围直到找到最小的时间

其中二分法的复杂度是 O(logn)、dfs 的复杂度是 O(n^2)

所以这个方法的时间复杂度就是 O(n^2 logn)

Javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
    const len = grid.length
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    const canReachInTime = (time) => {
        const visited = Array.from({ length: len }, _ => Array(len).fill(false))

        const dfs = (x, y) => {
            if (x === len - 1 && y === len - 1) {
                return true
            }
            visited[x][y] = true

            for (const [dx, dy] of dirs) {
                const nx = x + dx
                const ny = y + dy
                if (nx >= 0 && nx < len && ny >= 0 && ny < len &&
                    !visited[nx][ny] && grid[nx][ny] <= time) {
                        if(dfs(nx, ny)) {
                            return true
                        }
                }
            }
        }

        return dfs(0, 0)
    }

    // possible time range
    let left = Math.max(grid[0][0], grid[len - 1][len - 1])
    let right = len * len - 1

    while (left < right) {
        let mid = (left + right) >> 1
        if (canReachInTime(mid)) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
};

dijkstra + priority queue

第二个方法我们用 dijkstra 来找图上两点的最短路径

dijkstra 算法的思想就是每次从已到达的点中选择它们与未到达的点的边中最小的边来搜索

所以我们要借用小顶堆来辅助

算法步骤如下：

1. 我们先将 grid[0][0] 放入 minHeap 中
2. 然后我们对 minHeap 进行遍历
3. 每次遍历都取出当前堆顶元素（同时该元素也是当前堆里面最小的元素）
4. 如果当前元素已经经过了，则忽略当前元素，返回步骤 3
5. 如果当前元素已经到达了 grid[n - 1][n - 1]，则直接返回当前所需时间
6. 否则将当前元素的相邻元素全部放入堆中，返回步骤 3

其中小顶堆每次入栈或出栈的复杂度是 O(logn)、对 grid 遍历的复杂度是 O(n^2)

所以这个方法的时间复杂度就是 O(n^2 logn)

Javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var swimInWater = function (grid) {
    const len = grid.length
    // [time, x, y]
    const minHeap = new PriorityQueue((a, b) => a[0] - b[0])
    const visited = Array.from({ length: len }, _ => Array(len).fill(false))
    const dirs =[[0, 1], [0, -1], [1, 0], [-1, 0]] 

    minHeap.enqueue([grid[0][0], 0, 0])

    while(!minHeap.isEmpty()) {
        const [time, x, y] = minHeap.dequeue()
        if(visited[x][y]) {
            continue
        }
        visited[x][y] = true

        if(x === len - 1 && y === len - 1) {
            return time
        }

        for(const [dx, dy] of dirs) {
            const nx = x + dx
            const ny = y + dy
            if(nx >=0 && nx < len && ny >=0 && ny < len && !visited[nx][ny]) {
                minHeap.enqueue([Math.max(grid[nx][ny], time), nx, ny])
            }
        }
    }
};