算法题总结

1、接雨水 Leetcode

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

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

输入：height = [4,2,0,3,2,5]
输出：9

## 解题思路
## 针对每一个高度数字，其可以蓄水的多少是由其左侧最高，右侧最高决定的。因此，针对每一个数字，我们寻找其左侧最大值max_left和右侧最大值max_right，
## 该位置可以蓄水量为 min(max_left, max_right)- height[i]

class Solution:
    def trap(self, h: List[int]) -> int:
        maxl = maxr = 0
        n = len(h)
        list_ = [0] * n

        for i in range(n):
            maxl = max(maxl, h[i]) # 针对每一个index i，记录其左侧最大值
            list_[i] = maxl
        for i in range(n-1, -1, -1):
            maxr = max(maxr, h[i])  # 针对每一个index i，记录其右侧最大值
            list_[i] = min(list_[i], maxr)  # 针对每一个index i，记录min(max_left, max_right)
            h[i] = list_[i] - h[i]  # 记录蓄水量

        return sum(h)