每日一题 1631. 最小体力消耗路径（中等，最小最大值）

本文主要是介绍每日一题 1631. 最小体力消耗路径（中等，最小最大值），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 最小最大值问题，二分答案搜索
2. heights的最大值为10⁶，所以右边界为10⁶，左边界为0，通过dfs来判断是否存在一条路径，其中所有的相邻格子的高度差绝对值小于左右边界的中点

class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:l, r = 0, 10**6 - 1vis = set()def dfs(i, j, m):if (i, j) in vis:return Falseif i == len(heights) - 1 and j == len(heights[0]) - 1:return Truevis.add((i, j))if i + 1 < len(heights) and abs(heights[i + 1][j] - heights[i][j]) <= m:if dfs(i + 1, j, m):return Trueif i - 1 >= 0 and abs(heights[i - 1][j] - heights[i][j]) <= m:if dfs(i - 1, j, m):return Trueif j + 1 < len(heights[0]) and abs(heights[i][j + 1] - heights[i][j]) <= m:if dfs(i, j + 1, m):return Trueif j - 1 >= 0 and abs(heights[i][j - 1] - heights[i][j]) <= m:if dfs(i, j - 1, m):return Truereturn Falsewhile l < r:vis.clear()m = (l + r) >> 1if dfs(0, 0, m):r = melse:l = m + 1return l

这篇关于每日一题 1631. 最小体力消耗路径（中等，最小最大值）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---