首页 > 代码库 > [leetcode] Trapping rain water
[leetcode] Trapping rain water
42. 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.
Solution:
Sum water amount of each bin (width=1). Maintain a height of left and right seperately, which is like a one-side wall of partial container. Fix the higher one and add the water amount regard to the lower part.
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ left, right = 0, 0 start, end = 0, len(height)-1 result = 0 while start <= end: if left<right: if height[start]>=left: left = height[start] else: result += left - height[start] start += 1 else: if height[end]>=right: right = height[end] else: result += right - height[end] end -= 1 return result
[leetcode] Trapping rain water
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。