Leetcode Trapping Raining water

这题没能想出来 , 看的题解 , 遍历一遍把水坑用水泥填上 , 计算面积 , 再遍历一遍原来的面积 , 用填了水泥的面积 - 原来的面试 = 答案

iterate origin
    find maxIndex

filled=[]
max=origin[0]
iterate from left to maxIndex
    if origin[i]<max
        filled[i]=max
    else 
        max=arr[i]
        filled[i]=max

max=origin[len-1]
from right to maxIndex
    if origin[i]<max
        filled[i]=max
    else 
        max=arr[i]
        filled[i]=max

sumFilled = sum(filled)
sumOrigin = sum(origin)

res=sumFilled-sumOrigin

return res
func trap(height []int) int {
    if len(height)==0 {
        return 0
    }
    max:=height[0]
    maxIndex:=0
    for k,v:=range height {
        if v>max {
            max=v
            maxIndex=k
        }
    }

    filled:=make([]int,len(height))
    max1:=height[0]

    for i:=0;i<maxIndex;i++ {
        if height[i]<max1 {
            filled[i]=max1
        } else {
            max1=height[i]
            filled[i]=max1
        }
    }

    endIndex:=len(height)-1
    max2:=height[endIndex]
    for j:=endIndex;j>=maxIndex;j-- {
        if height[j]<max2 {
            filled[j]=max2
        } else {
            max2=height[j]
            filled[j]=max2
        }
    }

    sumFilled:=0
    for _,v:=range filled {
        sumFilled+=v
    }

    sumOrigin:=0
    for _,v:=range height {
        sumOrigin+=v
    }

    return sumFilled-sumOrigin

}
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!