题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
接雨水 - 图1
上面是由数组 [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

方案一

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         if not height:
  4.             return 0
  5.         # 遍历一次找到最高的柱子的高度
  6.         _max = max(height)
  8.         res = 0
  9.         # 从前往后遍历
  10.         p1 = 0 # 前一个低的柱子的高度，上图中 index = 1, 3, 7
  11.         for i in range(len(height)):
  12.             if height[i] == _max:
  13.                 break
  14.             if p1 == 0 or height[i] >= p1:
  15.                 p1 = height[i]
  16.                 continue
  17.             res = res + p1 - height[i]
  18.         # 从后往前遍历
  19.         p2 = 0
  20.         for j in range(len(height) - 1, -1, -1):
  21.             if height[j] == _max:
  22.                 break
  23.             if p2 == 0 or height[j] >= p2:
  24.                 p2 = height[j]
  25.                 continue
  26.             res = res + p2 - height[j]
  28.         # 有多个最高点
  29.         if i != j:
  30.             for k in range(i + 1, j):
  31.                 res = res + _max - height[k]
  33.         return res
  • 时间复杂度接雨水 - 图2
  • 迭代过程中 res = res + before_height(前一个较高的柱子的高度) - currnet_height(当前柱子的高度)

    方案二（leetcode）

  1. class Solution:
  2.     def trap(self, height: List[int]) -> int:
  3.         if not height:
  4.             return 0
  5.         n=len(height)
  6.         left,right=0,n-1
  7.         ans=0
  8.         maxleft=height[0]
  9.         maxright=height[n-1]
  10.         while left<right:
  11.             maxleft=max(maxleft,height[left])
  12.             maxright=max(maxright,height[right])
  13.             if maxleft<maxright:
  14.                 ans+=maxleft-height[left]
  15.                 left+=1
  16.             else:
  17.                 ans+=maxright-height[right]
  18.                 right-=1
  19.         return ans