Lintcode

原题目地址

描述

给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。

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.

样例

样例 1: 输入: [0,1,0] 输出: 0

样例 2:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

挑战

O(n) 时间, O(1) 空间O(n) 时间, O(n) 空间也可以接受

思路

计算柱子I能承接多少水，其实就是寻找左边最大的极值LeftMax[I]，右边最大的极值RightMax[I]；在水不漏掉的情况下，即左右两边的最大极值大于height[I]得到每根柱子能承接的水量 min(LeftMax[I], RightMax[I]) - height[I]

代码

在实际操作中，将一次寻找左边最大值的遍历 和 最后的计算合并

class Solution: """ @param heights: a list of integers @return: a integer """ def trapRainWater(self, heights): length = len(heights) if length < 2: return 0 leftMax = [] rightMax = [] # for i in range(length): # if i == 0: # leftMax.append(0) # elif i == 1: # leftMax.append(heights[0]) # else: # leftMax.append(max(leftMax[i - 1], heights[i - 1])) for i in range(length - 1, -1, -1): if i == length - 1: rightMax.append(0) elif i == length - 2: rightMax.append(heights[length - 1]) else: rightMax.append(max(heights[i + 1], rightMax[length - i - 2])) # rightMax.reverse() # print(rightMax) rain = 0 for i in range(length): if i == 0: leftMax.append(0) rain += 0 continue elif i == 1: leftMax.append(heights[0]) else: leftMax.append(max(leftMax[i - 1], heights[i - 1])) if leftMax[i] > heights[i] and rightMax[length-i-1] > heights[i]: rain += min(leftMax[i], rightMax[length-i-1]) - heights[i] # print(leftMax) return rain if __name__ == '__main__': print(Solution().trapRainWater([1, 3, 4, 5, 2, 4, 7, 4, 3]))