这题没能想出来 , 看的题解 , 遍历一遍把水坑用水泥填上 , 计算面积 , 再遍历一遍原来的面积 , 用填了水泥的面积 - 原来的面试 = 答案
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
}
网友评论