Every time, just find the next height that can hold water with the current height, it can only be two situations:
- A height after current index, that is higher then current height
- No heights after current index is higher than current height, then just pick the highest to hold water with current height.
The code is more clear to understand.
# A simple and fast python solution (46 ms, beats 99%+) class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ if not height or len(height) < 3: return 0 result = 0 current_index = 0 next_index = -1 while current_index < len(height) - 1: next = self.findnext(height, current_index) if height[next] > height[current_index]: # current_index determines the height of water trapped in this segment for i in range(current_index + 1, next): result += height[current_index] - height[i] else: # "next" determines the height of water trapped in this segment for i in range(current_index + 1, next): result += height[next] - height[i] current_index = next return result def findnext(self, height, current): # find the next index in "height" that can hold water with "current" next = -1 for i in range(current + 1, len(height)): if height[i] >= height[current]: return i else: if next < current: next = i else: if height[i] >= height[next]: next = i return next