# Ruby leetcode 上的一道题，有没有更简单的解法？

wudixiaotie · 2014年11月13日 · 最后由 catfish23 回复于 2018年08月28日 · 2376 次阅读

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

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!

===============================下面是我的解法======================================= 大概思路是遍历每个节点，找到左边最高边界，找到右边最高边界，然后取这两个边界中最小的和当前高度做差，就是当前的点的蓄水量。每个点蓄水量之和就是总的蓄水量。

``````a = [0,1,0,2,1,0,1,3,2,1,2,1]
b = [0,0,0,0,0,7,0,0,0,0,0,0]
# https://oj.leetcode.com/problems/trapping-rain-water/
def trap(data_arr)
total_trap = 0

data_arr.each_with_index do |item, index|
left_edge, right_edge = item, item
# find left bigest edge
(0..(index - 1)).reverse_each do |left_index|
left_item = data_arr[left_index]
if left_item > left_edge
left_edge = left_item
end
end

# find right bigest edge
((index + 1)..(data_arr.length - 1)).each do |right_index|
right_item = data_arr[right_index]
if right_item > right_edge
right_edge = right_item
end
end

# this point traped water
increment = left_edge >= right_edge ? right_edge - item : left_edge - item

# puts "index:#{index} left_edge:#{left_edge} right_edge:#{right_edge} increment:#{increment}"
total_trap += increment
end

total_trap
end

p trap(a) == 6 # =》 true
p trap(b) == 0 # =》 true
``````

============================================================================================== 或者有什么办法把代码简化？

``````map = [0,1,0,2,1,0,1,3,2,1,2,1]
result = 0
map.max.times.each do
cursor = -1
map = map.each_with_index.map do |v, i|
if v != 0
v-=1
result += i - cursor - 1 if cursor>0 and cursor != i
cursor = i
end
v
end
end
p result
``````

``````def trap(map=[])
left = 0
right = map.length - 1
traps = 0
while(left < right)
min = [map[left], map[right]].min
if(map[left] == min)
left += 1
while((left < right) && (map[left] < min))
traps += min - map[left]
left += 1
end
else
right -= 1
while((left < right) && (map[right] < min))
traps += min - map[right]
right -= 1
end
end
end
return traps
end
``````

[0,1,0,2,1,0,1,3,2,1,2,1] 夹着 2 个 0, 然后非 0 项全部减去 1 [0,0,0,1,0,0,0,2,1,0,1,0] 夹着 4 个 0，然后非 0 项全部减去 1 [0,0,0,0,0,0,0,1,0,0,0,0] 没夹着 0，结束