Leetcode 42. Trapping Rain Water

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

1. Description

2. Solution

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

• Version 1

代码语言：javascript复制

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

代码语言：javascript复制

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

代码语言：javascript复制

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/

sdn com version 博客 优化

0 人点赞