title
You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.
Constraints:
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106
solution
除了uf还有一种dijkstra 可以看
作法： 优先队列+uf
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
uf = {}
def find(x):
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def is_connect(a, b):
return find(a) == find(b)
def union(a, b):
uf[find(a)] = find(b)
m, n = len(heights), len(heights[0])
from heapq import heappush, heappop
h = []
for i in range(m):
for j in range(n):
u = (i, j)
uf[u] = u
v = (i, j + 1)
if v[1] < n:
heappush(h, (abs(heights[v[0]][v[1]] - heights[u[0]][u[1]]), u, v))
v = (i + 1, j)
if v[0] < m:
heappush(h, (abs(heights[v[0]][v[1]] - heights[u[0]][u[1]]), u, v))
while h:
d, u, v = heappop(h)
union(u, v)
if is_connect((0,0), (m-1, n-1)):
return d
return 0
最开始不是下述这种作法，利用二分法及uf timeout,
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
self.uf = {}
def find(x):
self.uf.setdefault(x, x)
if self.uf[x] != x:
self.uf[x] = find(self.uf[x])
return self.uf[x]
def is_connect(a, b):
return find(a) == find(b)
def union(a, b):
self.uf[find(a)] = find(b)
n = len(heights)
if n == 0:
return 0
cols = len(heights[0])
import math
max_diff = 0
for i in range(n):
for j in range(cols):
if i + 1 < n:
max_diff = max(max_diff, math.fabs(heights[i + 1][j] - heights[i][j]))
if j + 1 < cols:
max_diff = max(max_diff, math.fabs(heights[i][j + 1] - heights[i][j]))
def is_valid(effort):
self.uf = {}
for i in range(n):
for j in range(cols):
if i + 1 < n and math.fabs(heights[i + 1][j] - heights[i][j]) <= effort:
union(p(i, j), p(i + 1, j))
if j + 1 < cols and math.fabs(heights[i][j + 1] - heights[i][j]) <= effort:
union(p(i, j + 1), p(i, j))
return is_connect(p(0, 0), p(n - 1, cols - 1))
def p(x, y):
return (x, y)
# return n * x + y
left, right = 0, max_diff
while left < right:
mid = left + (right - left) // 2
if is_valid(mid):
right = mid
else:
left = mid + 1
return int(right)