Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
func maxArea(height []int) int {
m:=0
len:=len(height)
for i,j:=0,len-1 ; i<len && j>=0 ; {
area:=(j-i)*min(height[i],height[j])
m=max(m,area)
if height[i] <= height[j]{
i++
}else{
j--
}
}
return m
}
func min(i int ,j int ) int {
if i<=j {
return i;
}
return j
}
func max(i int ,j int ) int {
if i>=j {
return i;
}
return j
}
最好不要暴力搜索,暴力搜索的时间级别在O(n2),利用贪心算法的思路,可以优化到O(n)左右,基本思路是在每次循环的时候去掉左右最矮的边取的局部最优解,然后与max比较,最后的结果就是全局最优解