容器盛水问题
容器盛水问题
http://www.nowcoder.com/questionTerminal/31c1aed01b394f0b8b7734de0324e00f
使用双指针
此题可以理解为水位动态变换
定义左右指针i,j，以及水位标记mark，随着指针的移动，水位标记会改变。也就是说，这题中含有指针的移动规则以及水位mark的改变规则。
指针移动规则：移动水位小的指针，详情见https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/
水位改变规则：当指针移动后，此时移动后的指针所指水位大于标记水位时，更新标记水位为指针所指水位中较小的。
func maxWater( arr []int ) int64 {
// write code here
sum := 0
i:=0
j:=len(arr)-1
mark := getmin(arr[i],arr[j])
for i<j{
if arr[i] > arr[j]{
j--
if mark > arr[j]{
sum += mark-arr[j]
}else{
mark = getmin(arr[i],arr[j])
}
}else{
i++
if mark >arr[i]{
sum += mark-arr[i]
}else{
mark = getmin(arr[i],arr[j])
}
}
}
return int64(sum)
}
func getmin(a,b int)int{
if a>b{
return b
}else{
return a
}
} 