Ruby leetcode 上的一道题，有没有更简单的解法？
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
简单的游标方式，没有包装成方法，你看行不行？
我想到的也是楼主的左右各遍历一次。。。
分享 一个 O(n) 的：(改自别人的 java 代码)
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，结束
思想就是从最底下一层一层往上数，每到第 i 层，然后看夹着几个 0 就是看这一层 (而且是如果只有这一层) 能存储几格水，所以 [0,1,0,2,1,0,1,3,2,1,2,1] 也可以把非 0 项都变成 1，[0,1,0,1,1,0,1,1,1,1,1,1]，这样再看夹着几个 0，本质上就是考虑单独这一层，但是上面直接看夹着几个 0，结果是一样的。
然后到下一层 i+1, 但要把下一层当做最底层，所以非 0 项都减去 1，作为下一层的数组。
这是我直觉想到的办法，不知道有没有没有考虑到的极端情况。而且这算法复杂度是 O(n*h)，n 是数组长度，h 是最大层数，估计也不是最好的办法。
