42. 接雨水

DP:

  1.  这题的解题思路来源于暴力法,对于每一点,其积累的雨水等于 min(left_max,right_max) - height[i]

  2.  而对于自身就是left_max或right_max时,显然相减等于0

2. 双指针

  1. 使用本方法最重要的一点是想通,从左右两端找left_max,right_max意味着,中间出现的高柱子,是对左右两边的蓄水量没有影响的

  2. 如果中间高,则update left_max 或 right_max, 如果中间小,则蓄水 min(left_max,right_max)- height[i]

  3. 操作方法:

    1) 左右指针 left,right = 0 , len(height) -1

    2)   左右的dp值  left_max = right_max = -1

    3)   一遍遍历height ,更新 left_max 与 right_max,同时将差值装入 res 

  

原文地址:https://www.cnblogs.com/ChevisZhang/p/13671372.html