Share my python solution


  • 0
    R
    class Solution:
        # @param {integer[]} height
        # @return {integer}
        def trap(self, height):
            if not height:
                return 0
            
            s = []
            water_vol = 0
            for i, n in enumerate(height):
                if not s:
                    # until we find 1st bar starting to decrease height, we add it into stack
                    if (i < len(height)) and (i+1 < len(height)) and (height[i] > height[i+1]):
                        s.append((i, n))
                else:
                    if n < s[-1][1]:
                        # current height less than the previous height, keep adding it
                        s.append((i, n))
                    elif n == s[-1][1]:
                        # current height equal to the previous height, only keep the current one
                        s.pop()
                        s.append((i, n))
                    else:
                        # current height larger than the previous height, start to compute local sub-volumes
                        # until all previous uncomputed sub-volumes are computed
                        s.append((i, n))
                        tmp_vol, s = self.utilLocalWaterVolume(s)
                        while tmp_vol > 0:
                            water_vol += tmp_vol
                            tmp_vol, s = self.utilLocalWaterVolume(s)
                            
            # if stack is not empty after traversing all elems,
            # computed leftover uncomputed sub-volumes
            tmp_vol, s = self.utilLocalWaterVolume(s)
            while tmp_vol > 0:
                water_vol += tmp_vol
                tmp_vol, s = self.utilLocalWaterVolume(s)
            
            return water_vol
    
        def utilLocalWaterVolume(self, s):
            # stack has less than 3 elevations, return 0
            if len(s) < 3:
                return 0, s
                
            # each time we pick 3 consecutive heights to compute local sub-volumes 
            x = s[-3:]
            depth = min(x[0][1], x[2][1]) - x[1][1]
            width = x[2][0] - x[0][0] - 1
            vol = depth*width
            
            # heights are not in the right pattern to hold water, return 0
            if depth <= 0:
                return 0, s
            
            # after computing sub-volume, we "fill" the gap with water by updating
            # their heights and remove duplicate heights
            if x[0][1] != x[2][1]:
                del s[-3:]
                tmp = [(x[0][0], x[0][1]),(x[2][0], x[2][1])]
                s = s + tmp
            else:
                del s[-3:]
                s.append((x[2][0], x[2][1]))
            
            return vol, s
    

    This solution scans the height array one time, only using a stack to store the currently unsolved sub-volumes. It is inspired by the problem of find rectangle with maximal area under a histogram.


Log in to reply
 

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