1631. Path with Minimum Effort

Medium

Description

給定一個 m x n 的高度矩陣 heights，從左上角走到右下角。路徑的「effort」定義為路徑中相鄰格子高度差的最大值。求最小 effort 的路徑。

Example:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2

Intuition#

最小化路徑上的最大邊權 – 用修改版的 Dijkstra，距離定義為路徑上的最大高度差。

不是求路徑總和最小，而是求路徑上最大邊權最小
修改 Dijkstra：dist[next] = min(dist[next], max(dist[cur], |h[cur] - h[next]|))
也可以用二分搜尋 + BFS/DFS

Approaches#

⭐1: 修改版 Dijkstra#

概念: 用最小堆，每次取出 effort 最小的節點。effort = max(目前 effort, 相鄰高度差)
時間複雜度: O(m * n * log(m * n))
空間複雜度: O(m * n)

class Solution {
    fun minimumEffortPath(heights: Array<IntArray>): Int {
        val m = heights.size
        val n = heights[0].size
        val dist = Array(m) { IntArray(n) { Int.MAX_VALUE } }
        dist[0][0] = 0
        val pq = java.util.PriorityQueue<IntArray>(compareBy { it[0] })
        pq.add(intArrayOf(0, 0, 0)) // effort, row, col
        val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

        while (pq.isNotEmpty()) {
            val (effort, r, c) = pq.poll()
            if (r == m - 1 && c == n - 1) return effort
            if (effort > dist[r][c]) continue

            for ((dr, dc) in dirs) {
                val nr = r + dr
                val nc = c + dc
                if (nr in 0 until m && nc in 0 until n) {
                    val newEffort = maxOf(effort, Math.abs(heights[r][c] - heights[nr][nc]))
                    if (newEffort < dist[nr][nc]) {
                        dist[nr][nc] = newEffort
                        pq.add(intArrayOf(newEffort, nr, nc))
                    }
                }
            }
        }
        return 0
    }
}

2: 二分搜尋 + BFS#

概念: 二分搜尋答案 effort，用 BFS 驗證是否存在 effort 以內的路徑
時間複雜度: O(m * n * log(maxHeight))
空間複雜度: O(m * n)

class Solution {
    fun minimumEffortPath(heights: Array<IntArray>): Int {
        val m = heights.size
        val n = heights[0].size
        var lo = 0
        var hi = 1_000_000

        while (lo < hi) {
            val mid = (lo + hi) / 2
            if (canReach(heights, m, n, mid)) hi = mid
            else lo = mid + 1
        }
        return lo
    }

    private fun canReach(heights: Array<IntArray>, m: Int, n: Int, maxEffort: Int): Boolean {
        val visited = Array(m) { BooleanArray(n) }
        val queue = ArrayDeque<IntArray>()
        queue.add(intArrayOf(0, 0))
        visited[0][0] = true
        val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

        while (queue.isNotEmpty()) {
            val (r, c) = queue.removeFirst()
            if (r == m - 1 && c == n - 1) return true
            for ((dr, dc) in dirs) {
                val nr = r + dr
                val nc = c + dc
                if (nr in 0 until m && nc in 0 until n && !visited[nr][nc]) {
                    if (Math.abs(heights[r][c] - heights[nr][nc]) <= maxEffort) {
                        visited[nr][nc] = true
                        queue.add(intArrayOf(nr, nc))
                    }
                }
            }
        }
        return false
    }
}

🔑 Takeaways#

Pattern: 最小化最大邊權路徑 – 修改 Dijkstra 的鬆弛條件
關鍵技巧: Dijkstra 中 dist[v] = min(dist[v], max(dist[u], w(u,v))) 處理 minimax 路徑；二分搜尋 + BFS 是替代方案