LeetCode 筆記 - 778. Swim in Rising Water

Posted on

題目在此 778. Swim in Rising Water

給定一個 m x n 的整數矩陣 grid，其中每個元素代表該位置的高度。你從左上角 (0, 0) 開始，目標是到達右下角 (m-1, n-1)。你可以向上、下、左、右移動，但只能在當前時間 t 大於或等於你所在位置的高度時才能移動。

請找出到達目標位置右下角所需的最小時間 t。

LeetCode 778. Swim in Rising Water

解題思維

這題可以使用 Dijkstra 演算法 來解決，因為我們需要找到一條從起點到終點的路徑，使得路徑上所有位置的最大高度（即所需的時間 t）最小化。

具體來說，我們可以使用一個最小堆（min-heap）來優先處理當前時間 t 最小的位置。每次從堆中取出當前時間 t 最小的位置，然後檢查其四個相鄰位置。如果相鄰位置尚未訪問過，則計算到達該位置所需的時間 t（即當前時間 t 與該位置高度的最大值），並將其加入堆中。

Time complexity 是 $O((m \times n) \times\log(m \times n))$
因為我們最多會處理 m * n 個位置，而每次插入和取出堆的時間複雜度是 $O(\log(m \times n))$。

Space complexity 是 $O(m \times 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
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:

        # step 0: we use Dijkstra algorithm
        # step 1: Because the min-heap always gives us the path with the lowest cost (t), the first time we reach the destination, we are guaranteed to have found the minimum time.

        # NOTE: m = len(grid), n = len(grid[0])
        # time complexity: O((m * n) * log (m * n))
        # space complexity: O(m * n)

        y = m = len(grid)
        x = n = len(grid[0])

        stack = [(grid[0][0], 0, 0)]
        visited = set((0, 0))

        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while stack:

            cur_t, cur_y, cur_x = heapq.heappop(stack) # O(log (m * n))

            if (cur_y, cur_x) == (y - 1, x - 1):
                return cur_t

            for dy, dx in direction:

                next_y = cur_y + dy
                next_x = cur_x + dx

                if not (0 <= next_y < y):
                    continue
                if not (0 <= next_x < x):
                    continue

                if (next_y, next_x) in visited:
                    continue
                visited.add((next_y, next_x))

                next_t = max(cur_t, grid[next_y][next_x])

                heapq.heappush(stack, (next_t, next_y, next_x))
        
        # we should never reach here
        return -1

也許你也會想看看