描述 给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。   在线评测地址：领扣题库官网   样例1 输入: [0,1,0] 输出: 0 样例2 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

解法思路

• 使用九章算法班中讲过的相向型双指针算法。 整个算法的思想是计算每个位置上可以盛放的水，累加起来。
• 记录如下几个值：
• left, right => 左右指针的位置
• left_max, right_max => 从左到右和从右到左到 left, right 为止，找到的最大的 height
• 每次比较 left_max 和 right_max，如果 left_max 比较小，就挪动 left 到 left + 1。 与此同时，查看 left 这个位置上能够盛放多少水，这里有两种情况：
• 一种是 left_max > heightsleft，这种情况下，水可以盛放 left_max - heightsleft 那么多。因为右边有 right_max 挡着，左侧可以到 left_max。
• 一种是 left_max <= heightsleft，这种情况下，水无法盛放，会从左侧流走，此时更新 left_max 为 heightsleft
• left_max >= right_max 的情况类似处理。

 

算法复杂度

• 时间复杂度：O(n)O(n)，空间复杂度 O(1)

class Solution: """ @param heights: a list of integers @return: a integer """ def trapRainWater(self, heights): if not heights: return 0   left, right = 0, len(heights) - 1 left_max, right_max = heights[left], heights[right] water = 0 while left <= right: if left_max < right_max: left_max = max(left_max, heights[left]) water += left_max - heights[left] left += 1 else: right_max = max(right_max, heights[right]) water += right_max - heights[right] right -= 1   return water 更多题解参考：九章solution