[leetcode/lintcode 题解] 阿里面试真题详解：接雨水

描述
给出 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