题目

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

示例 1：

leetcode 42 接雨水 (状态压缩DP也可解) - 图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 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1.暴力

  1. 初始化 ans=0ans=0
  2. 从左向右扫描数组：
  3. 初始化 \text{max_left}=0max_left=0 和 \text{max_right}=0max_right=0
  4. 从当前元素向左扫描并更新：
  5. \text{max_left}=\max(\text{max_left},\text{height}[j])max_left=max(max_left,height[j])
  6. 从当前元素向右扫描并更新：
  7. \text{max_right}=\max(\text{max_right},\text{height}[j])max_right=max(max_right,height[j])
  8. 将\min(\text{max_left},\text{max_right}) - \text{height}[i]min(max_left,max_right)−height[i] 累加到 \text{ans}ans

时间复杂度O(n2)

2.双指针

根据暴力法改进
由于每次都是找当前元素两边的最大值的比较小的一个,所以利用双指针,快速定位
定义left, right指针, left从左边扫描,right从右边开始扫描
定理:对left而言,left_max是可信的.对right而言,right_max是可信的
所以,从左边处理时,只要找到left_max反之,则通过right_max处理
时间复杂度O(n)

  1. const trap = function(height) {
  2.     //双指针法
  3.     let left = 0, 
  4.         right = height.length - 1,
  5.         res = 0,
  6.         left_max = 0,
  7.         right_max = 0
  8.     while (left <= right) {
  9.         if (left_max < right_max) {
  10.             res += Math.max(0, left_max - height[left])
  11.             left_max = Math.max(left_max, height[left])
  12.             left ++
  13.         } else {
  14.             res += Math.max(0, right_max - height[right])
  15.             right_max = Math.max(right_max, height[right])
  16.             right -- 
  17.         } 
  18.     }
  19.     return res
  20. };

3.单调栈

单调递减栈,形成中间洼地
第一次做的时候学(copy)的方法, 但还是忘了, 太菜了
思路,每次与前面元素比较,比它小的都可以根据栈顶元素和当前元素的较小的那个存水

  1. 从头开始扫描
  2. 如果stack不为空,将当前元素与栈顶元素比较,如果小于栈顶元素,说明它右边还没有墙壁让他盛水
  3. 如果大于栈顶元素,说明栈顶元素上方时可以盛水的
  4. 将栈顶元素出栈,(注意如果新的栈顶元素与之前的栈顶元素相等,也一起出栈可以减小时间复杂度)
  5. 计算盛水量(min(stack[stack.length - 1], height[i]) - height[top] ) * (i - stack[stack.length] - 1)

  6. 循环结束后,当前i入栈

    1. class Solution:
    2.  def trap(self, height: List[int]) -> int:
    3.      #每个柱子顶部的储水量：该柱子左右两侧最大值中最小的量减去该值（这里只计算这个柱子\
    4.      #顶部的水）然后累加
    5.      #单调栈方法
    6.      if not height: return 0
    7.      h_Len = len(height)
    8.      stack = []
    9.      res = 0
    11.      for i in range(h_Len):
    12.          while stack and height[stack[-1]] < height[i]:
    13.              bottom = height[stack.pop()]
    14.              #print(bottom)
    16.              while stack and height[stack[-1]] == bottom:
    17.                  stack.pop()
    18.              #print(stack)
    19.              #print("bottom",bottom)
    20.              #print(height[stack[-1]])
    21.              #print(min(height[stack[-1]], height[i]))
    22.              if stack:
    23.                  res += (min(height[stack[-1]], height[i]) - bottom) * (i - stack[-1] - 1)
    24.              #print(res)
    26.          stack.append(i)
    28.      return res

    4.动态规划

    未完待续…