25. Trapping Rain Water

func trap(height []int) int {
    n := len(height)
    maxLeft := make([]int, n)
    maxRight := make([]int, n)

    maxLeft[0] = height[0]
    for i := 1; i < n; i++ {
        maxLeft[i] = max(maxLeft[i-1], height[i])
    }

    maxRight[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        maxRight[i] = max(maxRight[i+1], height[i])
    }

    water := 0
    for i := 0; i < n; i++ {
        water += min(maxLeft[i], maxRight[i]) - height[i]
    }
    return water
}

func trap(height []int) int {
    left, right := 0, len(height)-1
    maxLeft, maxRight := 0, 0
    water := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] > maxLeft {
                maxLeft = height[left]
            } else {
                water += maxLeft - height[left]
            }
            left++
        } else {
            if height[right] > maxRight {
                maxRight = height[right]
            } else {
                water += maxRight - height[right]
            }
            right--
        }
    }
    return water
}