42-接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

---

示例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

---

解法

核心思路：使用双指针从两侧遍历,与当前的最大左右值相比，判断当前格子装了多少水。

class Solution:
    def trap(self, height: [int]) -> int:
        size = len(height)
        if size < 3: return 0
        left, right = 0, size - 1
        left_max, right_max = height[left], height[right]
        res = 0
        while left < right:
            if height[left] <= height[right]:
                if height[left] > left_max:
                    left_max = height[left]
                else:
                    res += left_max - height[left]
                left += 1

            else:
                if height[right] > right_max:
                    right_max = height[right]
                else:
                    res += right_max - height[right]
                right -= 1

        return res

---

来源

LeetCode中该题地址，Click here!