LC: 1102. Path With Maximum Minimum Value
https://leetcode.com/problems/path-with-maximum-minimum-value/
1102. Path With Maximum Minimum Value
Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.
The score of a path is the minimum value in that path.
For example, the score of the path
8 → 4 → 5 → 9is4.
Example 1:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. Example 2:
Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2Example 3:
Input: grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1000 <= grid[i][j] <= 109
Path With Maximum Minimum Value
The Essence:
Das Problem besteht darin, die größte Zahl aus einem Pfad in einer Menge der Pfade zu finden, die die Bedingung erfüllt: Es gibt einen Pfad zwischen dem Anfang und dem Ende, so dass der Mindestwert dieser Wert ist.
Die größte Zahl ist zwischen 0 und das Minimum von dem Anfangs- und Endwert des Pfads. Man kann daher dieses Intervall suchen.
Details:
Daraus kann man diesen Bereich binär durchsuchen, um den gesuchten Wert zu finden. Um zu überprüfen, ob der Wert einem Mindestwert auf einem Pfad ist, kann das Gitter mit diesem Wert als Grenzwert durchlaufen werden, wobei kein Feld mit niedrigerem Wert besucht wird.
Andere Ansätze, die Union-Find-Strukturen oder Prioritätswarteschlangen verwenden, sind ebenfalls möglich.
Solution(s) and Further Explanation:
Default Code:
Last updated