42.md

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.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.


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!

my thoughts:

1. two pointers beginning (p1) and end (p2). closer the pointers till cross in such a way: 1. move pointers till the next val decreases (current tallest edges); 2. compare heights at two pointers, use a third pointer (t) to count from the shorter edge till a taller edge on its side is found. go to 1.

my solution:

**********88 ms
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        res = 0
        l = len(height)
        p1, p2 = 0, l-1        
                
        while p1<p2:
            while p1<l-1 and height[p1]<=height[p1+1]:
                p1 += 1
            while p2>1 and height[p2]<=height[p2-1]:
                p2 -= 1
            #print( p1, p2, res )
            if height[p1]<=height[p2]:
                t = p1+1
                while t<p2 and height[t]<=height[p1]:
                    res += (height[p1] - height[t])
                    t += 1
                p1 = t
                    
            else:
                t = p2-1
                while t>p1 and height[t]<=height[p2]:
                    res += (height[p2] - height[t])
                    t -= 1
                p2 = t
                
        return res

my comments:

from other ppl's solution:

1. step 1 can be combined with step 2, only 1 while loop is needed to do the 2 steps at once, 69ms:
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        sum = 0
        start = 0
        end = len(height)-1
        while start < end:
            if height[start] <= height[end]:
                i = start + 1
                while i < end and height[i] <= height[start]:
                    sum += (height[start]-height[i])
                    i += 1
                start = i
            else:
                i = end -1
                while i > start and height[i] <= height[end]:
                    sum += (height[end]-height[i])
                    i -= 1
                end = i
        return sum