Trapping 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.

解题方法

从两边往里灌水，总是从低的那一边灌，而高的那一边保持不动，同时要记录下当前可以灌到的高度curBar, 及时更新

方法1

一开始直觉的方法是记录下每个位置能够灌到的位置，形成一个新的array，然后再用灌到的after的值减去原来的值

这就多了O(n)的space

方法2

其实不用新建一个array,在遍历的过程中直接将结果记录下来

Solution

第一次的方法，space O(n)

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        length = len(height)
        after = [0 for i in range(length)]
        left = 0
        right = length - 1
        curBar = min(height[left], height[right])
        while left <= right:
            curMin = min(height[left], height[right])
            if curMin > curBar:
                curBar = curMin
            after[left] = curBar
            after[right] = curBar
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        result = 0
        for i in range(length):
            result += max(0, after[i]-height[i])
        return result

第二次不需要新建array的方法

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        length = len(height)
        left = 0
        right = length - 1
        curBar = min(height[left], height[right])
        result = 0
        while left <= right:
            curMin = min(height[left], height[right])
            if curMin > curBar:
                curBar = curMin
            result += max(0, curBar - height[left])
            result += max(0, curBar - height[right])
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1


        return result

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:
                    # 比现有的bound低，可以灌
                    result += leftBound - heights[p1]
                else:
                    # 比现有的bound高，需要更新左边的bound
                    leftBound = heights[p1]
            else:
                p2 -= 1
                if heights[p2] < rightBound:
                    result += rightBound - heights[p2]
                else:
                    rightBound = heights[p2]

        return result

Reference