【Amazon面经】 Amazon OA 数据岗

兔精精 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.

最新回复 (1)
  • Crusader 6月前
    0 引用 2
    
    """
    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
    
返回