158 - 42 接雨水

题目

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

img

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

解答

https://github.com/Jancd/Leetcode-rust/blob/master/src/other/42.trap_the_rain.md

https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/

https://leetcode-cn.com/problems/trapping-rain-water/solution/wa-di-fa-by-huxixx/

挖地法

掐头去尾；所有数一起减掉两边更矮的墙，变成了负数的就是需要填水的空间。

不断重复即可

class Solution:
    def trap(self, height: List[int]) -> int:
        def removeHeadZero(l):
            while 1:
                if len(l) == 0 or l[0] > 0:
                    break
                else:
                    l.pop(0)

        def removeTailZero(l):
            while 1:
                if len(l) == 0 or l[-1] > 0:
                    break
                else:
                    l.pop(len(l)-1)

        def digDown(l):
            if not l:
                return
            minHeight = min(l[0], l[-1])
            i = 0
            while i < len(l):
                l[i] -= minHeight
                i += 1

        def calcWater(l):
            if len(l) <= 2:
                return 0
            removeHeadZero(l)
            removeTailZero(l)
            digDown(l)
            n = 0
            for i in range(0, len(l)):
                if l[i] < 0:
                    n -= l[i]
                    l[i] = 0
            return n+calcWater(l)

        return calcWater(height)

Runtime: 96 ms, faster than 5.76% of Python3 online submissions for Trapping Rain Water.

Memory Usage: 13.4 MB, less than 97.67% of Python3 online submissions for Trapping Rain Water.

动态规划

某点存的水，是左边最高墙和右边最高墙，之中比较矮的那个那个墙，减掉自己的高度。

左边最高墙：max_left [i] = Max(max_left [i-1],height[i-1])。右边同理

class Solution:
    def trap(self, height: List[int]) -> int:
        tol = 0
        mleft = [0]*len(height)
        mright = [0]*len(height)
        for i in range(1, len(height)):
            mleft[i] = max(mleft[i-1], height[i-1])
        for i in range(len(height)-2, -1, -1):
            mright[i] = max(mright[i+1], height[i+1])
        for i in range(1, len(height)):
            minNumb = min(mleft[i], mright[i])
            if minNumb > height[i]:
                tol += minNumb-height[i]
        return tol

Runtime: 56 ms, faster than 80.27% of Python3 online submissions for Trapping Rain Water.

Memory Usage: 13.3 MB, less than 97.67% of Python3 online submissions for Trapping Rain Water.

双指针

之前算当前点水量的算法，需要算出左边和右边的墙高。其实不需要知道那么多信息，只需要两条就够了：

1. 左边墙高度

2. 右边墙比左边墙高

那么此时就可以以左边墙为最深水量，再减掉自己的高度，就可以得到改点水量。

那么如何知道，右边比左边高呢？

就需要存两个变量，即下面的max_left和max_right。其实意思是，目前已知的左边/右边最高。

从两边往中间扫。比如先从左往右，如果遇到该点，高度比max_right更高，那么就把这个当作max_left，开始从右往左扫

class Solution:
    def trap(self, height: List[int]) -> int:
        tol = 0
        max_left = 0
        max_right = 0
        left = 1
        right = len(height)-2
        for i in range(1, len(height)):
            if height[left-1] < height[right+1]:
                max_left = max(max_left, height[left-1])
                m = max_left
                if m > height[left]:
                    tol += m-height[left]
                left += 1
            else:
                max_right = max(max_right, height[right+1])
                m = max_right
                if m > height[right]:
                    tol += m-height[right]
                right -= 1
        return tol

Runtime: 52 ms, faster than 89.94% of Python3 online submissions for Trapping Rain Water.

Memory Usage: 13.3 MB, less than 97.67% of Python3 online submissions for Trapping Rain Water.

func trap(height []int) int {
    var sum, ml, mr int
    left := 0
    right := len(height) - 1
    for left < right {
        if height[left] < height[right] {
            if height[left] >= ml {
                ml = height[left]
            } else {
                sum += ml - height[left]
            }
            left++
        } else {
            if height[right] >= mr {
                mr = height[right]
            } else {
                sum += mr - height[right]
            }
            right--
        }
    }
    return sum
}

Runtime: 4 ms, faster than 83.33% of Go online submissions for Trapping Rain Water.

Memory Usage: 2.8 MB, less than 100.00% of Go online submissions for Trapping Rain Water.

var trap = function(height) {
  let sum = 0,
    ml = 0,
    mr = 0,
    left = 0,
    right = height.length - 1
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= ml) {
        ml = height[left]
      } else {
        sum += ml - height[left]
      }
      left++
    } else {
      if (height[right] >= mr) {
        mr = height[right]
      } else {
        sum += mr - height[right]
      }
      right--
    }
  }
  return sum
};

Runtime: 60 ms, faster than 80.86% of JavaScript online submissions for Trapping Rain Water.

Memory Usage: 35 MB, less than 100.00% of JavaScript online submissions for Trapping Rain Water.

栈

用栈来保存每一堵墙。

• 当前高度小于等于栈顶高度，入栈

• 当前高度大于栈顶高度，出栈，计算积水

var trap = function(height) {
  let sum = 0
  stack = []
  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length -
        1]]) {
      let h = height[stack.pop()]
      if (stack.length === 0) {
        break
      }
      let distance = i - stack[stack.length - 1] - 1
      min = Math.min(height[stack[stack.length - 1]], height[i])
      sum += distance * (min - h)
    }
    stack.push(i)
  }
  return sum
};

Runtime: 68 ms, faster than 42.75% of JavaScript online submissions for Trapping Rain Water.

Memory Usage: 35.4 MB, less than 57.14% of JavaScript online submissions for Trapping Rain Water.