Trapping Rain Water

Hard

You are given an array of n non-negative integers where each element represents the height of a vertical bar in an elevation map. Every bar has a uniform width of 1. Your task is to determine how much water can be trapped after it rains. Imagine that the heights form a histogram where water can be trapped in the dips between taller bars. You need to compute the total amount of rainwater that can be collected between these bars. Input: - An integer array height of size n, where height[i] denotes the height of the i-th bar. Output: - Return a single integer representing the total volume of water that can be trapped. Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Example 2: Input: height = [4,2,0,3,2,5] Output: 9 Constraints: - 1 <= n <= 20,000 - 0 <= height[i] <= 100,000 - n == height.length

func trap(height []int) int {
    n := len(height)
    maxL := make([]int, n)
    maxR := make([]int, n)
    tempMaxL := 0
    tempMaxR := 0
    for i, j := 0, n-1; (i < n && j >= 0); i,j = i+1, j-1 {
        maxL[i] = tempMaxL
        maxR[j] = tempMaxR
        if (tempMaxL < height[i]) {
            tempMaxL = height[i]
        }
        if (tempMaxR < height[j]) {
            tempMaxR = height[j]
        }
    }
    totalWater := 0
    for i := 0; i < n; i++ {
        tempMin := min(maxL[i], maxR[i])
        diff := tempMin - height[i]
        if diff > 0 {
            totalWater = totalWater + diff
        }
    }
    return totalWater
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}