A simple and fast python solution (46 ms, beats 99%+)


  • 0
    T

    Every time, just find the next height that can hold water with the current height, it can only be two situations:

    1. A height after current index, that is higher then current height
    2. 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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.