ac solution


  • 0
    /*
         Solution1. time = O(n); space = O(1)
         <KEY POINT>: The key factor determining height[i] is min (leftEdge, rightEdge) for every step.
         height[i] = min (leftEdge, rightEdge) - A[i]
         */
        func trap(_ height: [Int]) -> Int {
            guard height.count > 0 else {return 0}
            let n = height.count
            var res: Int = 0
            var left = 0, right = n - 1
            var leftBound = -1, rightBound = -1
            while left <= right {
                leftBound = max(leftBound, height[left])
                rightBound = max(rightBound, height[right])
                // Barrel theory: Water is floating, so lower Bound of left/right bounds(one from leftMost, one from rightMost) decides the height of container
                if leftBound < rightBound {
                    res += leftBound - height[left]
                    left += 1
                } else {
                    res += rightBound - height[right]
                    right -= 1
                }
            }
            return res
        }
    

    0_1503687202744_TrappingWater.JPG


  • 0

    bang bang da


Log in to reply
 

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