【Leetcode】42. Trapping Rain Water-蒲公英云

【Leetcode】42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

题目大意：

根据已给的列表找出其中能够装水的部分，并求出储水量。

解题思路：

我将这个过程分成两个部分：（1）正向遍历这个序列，此时我们可以找出储水的部分都是左边的边界比右边的边界低或者一样高的区域。因此这些的判断条件都是①、下一个位置比当前的低则是Left ②、当前位置比Left高则为Right。

（2）反向遍历，我们可以找出储水的部分都是右边的边界比左边的边界低的区域。

两次相加就可以得出最终答案。

class Solution:
    def trap(self, height: List[int]) -> int:
        height.append(0)
        # print(height)
        state = False
        ans = 0
        R, L = 0, 0
        for i in range(len(height)-1):
            if state == False:
                if height[i] <= height[i+1]:
                    continue
                else:
                    state = True
                    L = i
                    continue
            else:
                if height[i] < height[L]:
                    R = i
                else:
                    R = R + 1
                    tmp_min = height[L]
                    if tmp_min > height[R]:
                        tmp_min = height[R]
                    tmp_ans = 0
                    for j in range(L+1,R):
                        tmp_ans += (tmp_min - height[j])
                    ans += tmp_ans
                    state = False
                if state == False:
                    if height[i] <= height[i + 1]:
                        continue
                    else:
                        state = True
                        L = i
                        continue
        state = False
        R, L = 0, 0
        height_re = height[:len(height)-1]
        # height_re.append(0)
        height_re.reverse()
        height_re.append(0)
        for i in range(len(height_re)-1):
            if state == False:
                if height_re[i] <= height_re[i+1]:
                    continue
                else:
                    state = True
                    L = i
                    continue
            else:
                if height_re[i] <= height_re[L]:
                    R = i
                else:
                    # 找槽完毕
                    R = R + 1
                    tmp_min = height_re[L]
                    if tmp_min > height_re[R]:
                        tmp_min = height_re[R]
                    tmp_ans = 0
                    for j in range(L+1,R):
                        tmp_ans += (tmp_min - height_re[j])
                    ans += tmp_ans
                    state = False
                if state == False:
                    if height_re[i] <= height_re[i + 1]:
                        continue
                    else:
                        state = True
                        L = i
                        continue
        if R == 0 and L == 0:
            return 0
        return ans