Python 59ms O(n) time O(n) space


  • 0
    Z

    class Solution(object):
    def trap(self, height):
    def left_max(heights):
    current_max = -1
    max_heights = []
    for height in heights:
    current_max = max(height, current_max)
    max_heights.append(current_max)
    return max_heights

        def right_max(heights):
            heights = list(heights)
            heights.reverse()
            max_heights = left_max(heights)
            max_heights.reverse()
            return max_heights
        
        left_heights = left_max(height)
        right_heights = right_max(height)
        heights = list(height)
        water_heights = [min(left_heights[i], right_heights[i]) for (i, height) in enumerate(height)]
        water_depth = [water_heights_i - height_i for water_heights_i, height_i in zip(water_heights, heights)]
        return sum(water_depth)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.