 #### 【Amazon面经】 AmazonOA数据岗

2020-6-22 970

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.`

• 6月前
2
``````
"""
Time: O(r+c)
Space: O(1)
"""

def maximum_score_path(matrix):

r = len(matrix)

if r < 1:
return 0

c = len(matrix)

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
``````