【LeetCode】 接雨水（python）

问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

1、找出最大的值以及最大值所在的索引：

		 max_v = max(height)
        max_index = height.index(max_v)

2、从i=0到max_index向后遍历数组，若当前值小于上一最大值说明接到雨水，若当前值大于上一最大值，则替换上一最大值为当前值：

		last = 0
        while i < max_index:
            if height[i] > last:
                last = height[i]
            elif height[i] < last:
                result += (last - height[i])
            i += 1

3、从j=len(height) - 1到max_index向前遍历数组，若当前值小于上一最大值说明接到雨水，若当前值大于上一最大值，则替换上一最大值为当前值：

 last = 0
        while j > max_index:
            if height[j] > last:
                last = height[j]
            elif height[j] < last:
                result += (last - height[j])
            j -= 1

完整代码

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        result = 0
        max_v = max(height)
        max_index = height.index(max_v)
        i = 0
        j = len(height) - 1
        last = 0
        while i < max_index:
            if height[i] > last:
                last = height[i]
            elif height[i] < last:
                result += (last - height[i])
            i += 1
        last = 0
        while j > max_index:
            if height[j] > last:
                last = height[j]
            elif height[j] < last:
                result += (last - height[j])
            j -= 1
        return result