Trapping Rain Water

问题：给定一个由非负整数组成的数组，数组元素代表柱体高度，求该数组所代表的这些柱体能容纳的水的体积

Trapping Rain Water

示例：

输入：[0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解决思路：遍历数组，使用变量保存当前最大值和位置。如果遍历到的元素不小于该值，（并且且如果两者位置间隔超过1，则计算两者之间可容纳的水的体积），则需要将当前最大值和位置替换掉；如果小于该值，则用另一变量保存需要去除的水底的体积

Python代码：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        self.area = 0
        length = len(height)
        l_index = self.cal_lr(0,length,1,height)
        self.cal_lr(length-1,l_index-1,-1,height)
        return self.area
    
    def cal_lr(self,s,e,interval,height):
        m_index,m_height,drown = s,0,0
        for i in range(s,e,interval):
            if height[i] >= m_height:
                if abs(i-m_index) > 1:
                    self.area += (abs(i-m_index)-1)*m_height-drown
                    drown = 0
                m_index = i
                m_height = height[i]
            else:
                drown += height[i]
        return m_index

Trapping Rain Water

相关推荐