LeetCode 42. 接雨水

题目

给定 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 个单位的雨水（蓝色部分表示雨水）。

方法：双指针法

由上图可知接雨水的多少取决于某位置左右最高的两个主子中更矮的那个柱子

• sum 记录接的雨水的数量

• 循环遍历数组 height，记录每个柱子所接的雨水数量

  • 因为第一个柱子和最后一个柱子不能接雨水，那么跳过
  • lHeight 表示某位置 i 左边存在的最高柱子高度，初始值为某位置 i 左边紧挨柱子的高度 height[i-1]；同理，rHeight 表示某位置 i 右边存在的最高柱子的高度，初始值为某位置 i 右边紧挨柱子的高度 height[i+1]
  • 循环遍历某位置 i 左边的所有柱子，记录最高柱子的高度 lHeight；同理，循环遍历某位置 i 右边的所有柱子，记录最高柱子的高度 rHeight
  • result 表示某个柱子所接雨水的数量，该值由其左右两边最高柱子高度的较小值 min(lHeight, rHeight) 减去当前柱子的高度 height[i] 决定。若 result 大于零，即表示可以接到雨水，那么将该雨水数量 result 加入总雨水数量 sum

• 返回接的总雨水数量 sum

class Solution(object):
    def trap(self, height):
        sum = 0 
        for i in range(len(height)):
            if i == 0 or i == len(height) - 1:
                continue
            lHeight = height[i-1]
            rHeight = height[i+1]
            for j in range(i-1):
                lHeight = max(lHeight, height[j])
            for j in range(i+2, len(height)):
                rHeight = max(rHeight, height[j])
            result = min(lHeight, rHeight) - height[i]
            if result > 0:
                sum += result
        return sum

参考

代码相关：https://programmercarl.com/0042.%E6%8E%A5%E9%9B%A8%E6%B0%B4.html