Trapping Rain Water

Question

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.

Trapping Rain Water

Example Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Challenge O(n) time and O(1) memory

O(n) time and O(n) memory is also acceptable.

Thoughts

这一道题属于2 pointer的题 通过观察我们可以发现，根据木桶原理，两个boundary中间能灌的水是取决于两边较小的值 通过可以灌到多少高度来求得水的体积是多少

设左右两个指针，从0和len(A)-1开始，从较小的一边往内部灌水

while loop, 当两个指针相遇时结束

• 如果小于boundary高度，计算能灌的水量
• 如果高于boundary的高度，更新这一边的boundary

Solution

class Solution:
    # @param heights: a list of integers
    # @return: a integer
    def trapRainWater(self, heights):
        # write your code here
        if not heights:
            return 0

        p1 = 0
        p2 = len(heights) - 1
        leftBound = heights[p1]
        rightBound = heights[p2]
        result = 0

        while p1 < p2:
            if leftBound <= rightBound:
                p1 += 1
                if heights[p1] <= leftBound:
                    result += leftBound - heights[p1]
                else:
                    leftBound = heights[p1]
            else:
                p2 -= 1
                if heights[p2] < rightBound:
                    result += rightBound - heights[p2]
                else:
                    rightBound = heights[p2]

        return result