Table of Content
题目如下：
思路：
这道题我推荐使用双指针的动态规划方法求解，通过动态更新左右的最大高度（决定容量的是左右最大高度中较小的那一个），来获取答案，可以单步调试看看求解的具体过程。
参考代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution: def trap(self, height): """ :type height: List[int] :rtype: int """ left = 0 right = len(height) - 1 res = 0 left_max = 0 right_max = len(height) - 1 while left < right: if height[left] > height[right]: if height[right_max] < height[right]: right_max = right right = right - 1 else: res += height[right_max] - height[right] right = right - 1 if height[left] <= height[right]: if height[left_max] < height[left]: left_max = left left = left + 1 else: res += height[left_max] - height[left] left = left + 1 return res |
