771. Gentlest Hike
A hiking club rates trails on a rectangular grid heights, where heights[r][c] is the elevation of a cell. A hiker starts at the top-left cell (0, 0) and must reach the bottom-right cell (rows - 1, cols - 1), stepping one cell at a time up, down, left or right. Cells may be revisited.
The strain of a hike is the largest absolute elevation difference between any two consecutive cells on it; the number of steps does not matter. Return the smallest possible strain over all hikes from the start to the finish. If the grid has a single cell, the answer is 0.
Example 1
- Input:
- heights = [[5,1,4],[8,2,9],[7,3,3]]
- Output:
- 4
- Explanation:
Route (0,0)=5, (0,1)=1, (1,1)=2, (2,1)=3, (2,2)=3 has steps 4, 1, 1, 0, so its strain is 4, and no route avoids a step of at least 4.
Example 2
- Input:
- heights = [[1,10],[1,10]]
- Output:
- 9
- Explanation:
Walking down the first column costs 0, but the last step across to the column of 10s must jump by 9, and every route has to make that jump once.
Example 3
- Input:
- heights = [[3,3,3,3]]
- Output:
- 0
- Explanation:
A single row of equal elevations needs no climbing at all, so the strain is 0.
Constraints
- 1 ≤ rows, cols ≤ 200
- 0 ≤ heights[r][c] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(R*C log(R*C))
- Space
- O(R*C)