42. leetcode题目讲解（Python）：接雨水(Trapping Rain Water)

题目如下：

题目：接雨水（Trapping Rain Water）

思路：

这道题我推荐使用双指针的动态规划方法求解，通过动态更新左右的最大高度（决定容量的是左右最大高度中较小的那一个），来获取答案，可以单步调试看看求解的具体过程。

参考代码：

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

源码地址：
https://github.com/jediL/LeetCodeByPython

其它题目：[leetcode题目答案讲解汇总（Python版 持续更新）]
(//www.greatytc.com/p/60b5241ca28e)

ps：如果您有好的建议，欢迎交流 :-D，
也欢迎访问我的个人博客 苔原带 (www.tundrazone.com)