LC42 - 接雨水

package DoublePointers

func trap(height []int) int {
    return trap1(height)
}

// 时间复杂度: O(n), 空间复杂度: O(n)
func trap1(height []int) int {
    size := len(height)
    lmax := make([]int, size)
    lmax[0] = height[0]
    for i := 1; i < size; i++ {
        lmax[i] = max(lmax[i-1], height[i])
    }
    rmax := make([]int, size)
    rmax[size-1] = height[size-1]
    for j := size - 2; j >= 0; j-- {
        rmax[j] = max(rmax[j+1], height[j])
    }
    result := 0
    for i := 1; i < size-1; i++ {
        limit := min(lmax[i-1], rmax[i+1])
        curVolume := max(0, limit-height[i])
        result += curVolume
    }
    return result
}

// 时间复杂度: O(n), 空间复杂度: O(1)
func trap2(height []int) int {
    left, right := 1, len(height)-2
    lmax, rmax := height[0], height[len(height)-1]
    result := 0
    for left <= right {
        if lmax <= rmax {
            result += max(0, lmax-height[left])
            lmax = max(lmax, height[left])
            left++
        } else {
            result += max(0, rmax-height[right])
            rmax = max(rmax, height[right])
            right--
        }
    }
    return result
}

每个格子的水位线取决于左侧最大高度和右侧最大高度的较小值。