Given a matrix with r rows and c columns, find the maximum score of a path starting at [0, 0] and ending at [r-1, c-1]. The score of a path is the minimum value in that path. For example, the score of the path 8 → 4 → 5 → 9 is 4.
Don't include the first or final entry. You can only move either down or right at any point in time.
Example 1:
Input: [[5, 1], [4, 5]]
Output: 4
Explanation:
Possible paths:
5 → 1 → 5 => min value is 1
5 → 4 → 5 => min value is 4
Return the max value among minimum values => max(4, 1) = 4.
Example 2:
Input: [[1, 2, 3] [4, 5, 1]]
Output: 4
Explanation:
Possible paths:
1-> 2 -> 3 -> 1
1-> 2 -> 5 -> 1
1-> 4 -> 5 -> 1
So min of all the paths = [2, 2, 4]. Note that we don't include the first and final entry.
Return the max of that, so 4.
收藏的用户（0）
X
正在加载信息~
最新回复 (1)
-
""" Time: O(r+c) Space: O(1) """ def maximum_score_path(matrix): r = len(matrix) if r < 1: return 0 c = len(matrix[0]) if c < 1: return 0 curr_min = float('inf') i = r - 1 j = c - 1 while not ((i - 1 == 0 and j == 0) or (j - 1 == 0 and i == 0)): if min(curr_min, matrix[i-1][j]) > min(curr_min, matrix[i][j-1]): curr_min = min(curr_min, matrix[i-1][j]) i -= 1 else: curr_min = min(curr_min, matrix[i][j-1]) j -= 1 return curr_min if __name__ == "__main__": input = [] print maximum_score_path(input) == 0 input = [[]] print maximum_score_path(input) == 0 input = [ [5, 1], [4, 5] ] print maximum_score_path(input) == 4 input = [ [1, 2, 3], [4, 5, 1] ] print maximum_score_path(input) == 4 input = [ [1, 2, 13, 22], [9, 5, 14, 17], [7, 8, 11, 3 ], [18, 35, 10, 1] ] print maximum_score_path(input) == 7 -
创作新主题