Three parts

- My plain solution
- Two pointers scanning by Sharing my simple c++ code: O(n) time, O(1) space
- Stack based solution by A stack based solution for reference, inspired by Histogram

The basic idea is: Find the valley, check the lower boundary (peak), and fill water.

My plain solution

```
# Solution - plain
def trap(height)
return 0 if height.length == 0
# make head and tail of height are peaks
pre_process!(height)
# find max element's index
max_ele, max_idx = -1, -1
height.each_with_index do |ele, idx|
next if max_ele >= ele
max_ele = ele
max_idx = idx
end
calc_trap(height[0..max_idx]) + calc_trap(height[max_idx..-1].reverse)
end
# Pre-condition: tail of height is the max element
def calc_trap(height)
return 0 if height.length < 3
n = height.length
pos = 0
res = 0
peak = height[0]
loop do
p1 = pos
pos += 1 while pos+1 < n && height[pos] >= height[pos+1]
pos += 1 while pos+1 < n && height[pos] <= height[pos+1]
p2 = pos
height[p1+1..p2].each do |ele|
next if peak <= ele
res += (peak - ele)
end
peak = height[pos] if peak < height[pos]
# puts "height: #{height}"
# puts "p1: #{p1} p2: #{p2}"
# puts "h1: #{height[p1]} h2: #{height[p2]}"
# puts "peak: #{peak}, res: #{res}"
break if pos+1 == n
end
res
end
def pre_process!(height)
n = height.length
# shift until the first peak
i = 0
i += 1 while i+1 < n && height[i] <= height[i+1]
# pop until the last peak
j = n-1
j -= 1 while j-1 >= 0 && height[j] <= height[j-1]
return 0 if i >= j
height[i..j]
end
```

Two pointers scanning by Sharing my simple c++ code: O(n) time, O(1) space

```
# Solution - two pointers
def trap(height)
left_max, right_max = 0, 0
head, tail = 0, height.length-1
water = 0
while head <= tail
left, right = height.values_at(head, tail)
if left <= right
left_max < left ? left_max = left : (water += left_max - left)
head += 1
else
right_max < right ? right_max = right : (water += right_max - right)
tail -= 1
end
end
water
end
d
```

Stack based solution by A stack based solution for reference, inspired by Histogram

```
# Solution - stack
def trap(height)
water = 0
stack = [] # used to store the index of height
i = 0
while i < height.length
if stack.empty? or height[i] <= height[ stack.last ]
stack << i
i += 1
else
valley = height[ stack.pop ]
next if stack.empty?
left_idx, right_idx = stack.last, i
peak = height.values_at(left_idx, right_idx).min
water += (peak - valley) * (right_idx - left_idx - 1)
end
end
water
end
```