Simple python solution


  • 0
    T
    class Solution(object):
        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            
            total = 0
            
            def getNextPeak(prev, height):
                if len(height) < 3 or prev + 1 >= len(height):
                    return -1
                
                i = prev + 1
                # todo, only finds if val is incresing. Needs to go unti
                maxIndex = i
                while (i < len(height) and height[i] <= height[prev]):
                    # also keep track of maximum value and index, since we will use that if no greater peak found
                    if height[i] >= height[maxIndex]:
                        maxIndex = i
                        
                    i += 1
                
                # handle case where we ran off the end of the list (didn't find a greater peak).
                if i >= len(height):
                    if maxIndex < len(height):
                        return maxIndex
                    else:
                        return -1
                else:
                    return i
            
            prevPeak = 0
            nextPeak = getNextPeak(prevPeak, height)
            while nextPeak >= 0:
                
                # get top of trap
                top = min(height[prevPeak], height[nextPeak])
                
                # add caught water to total.
                caught = [top - height[t] for t in range(prevPeak + 1, nextPeak) if top - height[t] > 0]
                total += sum(caught)
                
                prevPeak = nextPeak
                nextPeak = getNextPeak(prevPeak, height)
            
            return total
    

    Looking for constructive criticism on this solution. Thanks!


Log in to reply
 

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