【LeetCode】0042 接雨水

https://leetcode-cn.com/problems/trapping-rain-water/

# -*- coding:utf-8 -*-

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        if n <= 2:
            return 0
        left = 0
        right = n - 1
        sum = 0
        while left < right:
            if height[left] != 0 and height[right] != 0:
                min_flag = min(height[left], height[right])
                for i in range(left, right + 1):
                    if height[i] < min_flag:
                        sum += min_flag - height[i]
                        height[i] = min_flag
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return sum
if __name__ == '__main__':
    height = [0, 1, 0]
    print(Solution().trap(height))

思路： 类似于0011，左右指针向中间靠拢，找到当前可达容积然后改变数组值即可。