42. 接雨水

题目： Leetcode 42.接雨水 (二刷) （困难）

解题思路

本题的一个核心之一是木桶效应：取一个柱子两端较短的那个用作积水的参考。

核心之二是先选出最高的一个木板，然后分别从两边向最高木板过度，根据条件计算出积水量。

采用动态规划：

① 状态定义：即定义我们需要的参数，本地需要求最大积水量，可以看出是求全局最优解。因此我们定义一个
total_water来存储积水的最大值。left记录了每次动态计算的当前柱子左边的最高值，right记录了每次动态计算的当前
柱子右边的最高值。

② 状态转移方程：left = max(left,height[i-1]),right = max(right,height[i+1])

③ 初始化:首先去除首尾为0的值，计算出最高的柱子的索引。left=0,right=0

④ 选取结果：选取total_water作为最高的积水量

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        """木桶效应"""
        if not height:
            return 0
        # 求得最高的那一个大柱子的索引
        top_column = height.index(max(height))
        for i in range(top_column):
            if height[i] != 0:
                del height[:i]
                break
        for j in range(len(height)-1,top_column,-1):
            if height[j] != 0:
                del height[j+1:]
                break
        # 遍历最高值左边
        top_column = height.index(max(height))
        total_water = 0
        left = 0
        # 动态计算最大值
        # 遍历最高值左边
        for i in range(1,top_column):
            # 当前位置的前一个柱子的和其前面的最大值比较
            left = max(height[i-1],left)
            if height[i] < left:
                total_water += left-height[i]
        # 遍历最高值右边
        right = 0
        for i in range(len(height)-2,top_column,-1):
            right = max(height[i+1],right)
            if height[i] < right:
                total_water += right-height[i]
        return total_water