題目
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.
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!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
難度
Hard
方法
- 找到容器最高點位置max_height_index, 最高點高度max_height霹娄。找到最高點后浙于，左邊和右邊的bar都能跟其形成容器蓄水
- 從左往右處理至max_height_index, left_max記錄遍歷時左邊區(qū)間的最高高度, 如果height[i] > left_max, 則該格無法蓄水旦签，將left_max更新為height[i]; 如果height[i] < left_max垃帅，則該格可以蓄水left_max - height[i]
- 從右往左處理至max_height_index懂鸵，right_max記錄遍歷時右邊區(qū)間的最高高度，如果height[i] > right_max, 則該格無法蓄水，right_max更新為height[i]; 如果height[i] < right_max藕咏，則該格可以蓄水left_max - height[i]
- 將每格可以蓄的水累加即可
python代碼
# -*- coding:utf-8 -*-
class Solution(object):
def trap(self, height):
"""
1. 找到容器最高點位置max_height_index, 最高點高度max_height。找到最高點后秽五，左邊和右邊的bar都能跟其形成容器蓄水
2. 從左往右處理至max_height_index, left_max記錄遍歷時左邊區(qū)間的最高高度, 如果height[i] > left_max, 則該格無法蓄水孽查，
將left_max更新為height[i]; 如果height[i] < left_max，則該格可以蓄水left_max - height[i]
3. 從右往左處理至max_height_index筝蚕，right_max記錄遍歷時右邊區(qū)間的最高高度卦碾，如果height[i] > right_max, 則該格無法蓄水，
將right_max更新為height[i]; 如果height[i] < right_max起宽，則該格可以蓄水left_max - height[i]
4. 將每格可以蓄的水累加即可
:param height: List[int]
:return: int
"""
result = 0
max_height = 0
max_height_index = 0
for i in xrange(len(height)):
if height[i] > max_height:
max_height = height[i]
max_height_index = i
left_max = 0
for i in xrange(0, max_height_index):
if height[i] > left_max:
left_max = height[i]
else:
result += left_max - height[i]
right_max = 0
for i in xrange(len(height)-1, max_height_index, -1):
if height[i] > right_max:
right_max = height[i]
else:
result += right_max - height[i]
return result
assert Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
