Leetcode 42. Trapping Rain Water

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：总的留存的雨水等于每个柱子上留存的雨水，而每个柱子上留存的雨水等于其左边最高柱子与右边最高柱子中较矮柱子的高度减去其高度。Version 1超时，Version 2是以空间换时间，Version 3是对Version 2的进一步优化。

• Version 1

class Solution:
    def trap(self, height):
        length = len(height)
        evalation_map = [0] * length
        for i in range(length):
            self.trap_rain(evalation_map, i, height)

        return sum(evalation_map)


    def trap_rain(self, evalation_map, index, height):
        left = index
        right = index

        i = index
        while i >= 0:
            if height[i] > height[left]:
                left = i
            i -= 1

        if left == index:
            return
        i = index
        while i <= len(height) - 1:
            if height[i] > height[right]:
                right = i
            i += 1

        evalation_map[index] = min(height[left], height[right]) - height[index]

• Version 2

class Solution:
    def trap(self, height):
        length = len(height)
        evalation_map = [0] * length

        left = [i for i in range(length)]
        right = [i for i in range(length)]

        max_index = 0
        for i in range(length):
            if height[i] >= height[max_index]:
                max_index = i
            else:
                left[i] = max_index

        max_index = length - 1
        for i in range(length - 1, -1, -1):
            if height[i] >= height[max_index]:
                max_index = i
            else:
                right[i] = max_index

        for i in range(length):
            evalation_map[i] = min(height[left[i]], height[right[i]]) - height[i]

        return sum(evalation_map)

• Version 3

class Solution:
    def trap(self, height):
        left = 0
        right = len(height) - 1
        result = 0
        max_left_index = 0
        max_right_index = len(height) - 1
        while left < right:
            if height[left] < height[right]:
                if height[left] >= height[max_left_index]:
                    max_left_index = left
                else:
                    result = result + height[max_left_index] - height[left]
                left += 1
            else:
                if height[right] >= height[max_right_index]:
                    max_right_index = right
                else:
                    result = result + height[max_right_index] - height[right]
                right -= 1
        return result

Reference

1. https://leetcode.com/problems/trapping-rain-water/