Description
Find a path from top-left to bottom-right of a grid that minimizes the maximum absolute difference in heights between consecutive cells.
Examples
Input:
heights = [[1,2,2],[3,8,2],[5,3,5]]Output:
2Explanation:
Path 1->2->2->2->5 has max effort 2.
Input:
heights = [[1,3,5,7],[9,2,4,6],[8,1,3,2]]Output:
4Explanation:
The optimal path is 1->3->2->4->6->2 with efforts: |3-1|=2, |2-3|=1, |4-2|=2, |6-4|=2, |2-6|=4. The maximum effort is 4. Alternative paths have higher maximum efforts.
Input:
heights = [[4,4,4],[4,10,4],[4,4,4]]Output:
0Explanation:
The optimal path goes around the high center cell: 4->4->4->4->4->4->4 (going right, down, right, down). All consecutive cells have the same height, so all differences are 0, making the maximum effort 0.
Constraints
- •
1 ≤ rows, cols ≤ 100 - •
1 ≤ heights[i][j] ≤ 10⁶