题目如下:
实现思路:
- 暴力办法,简单粗暴,不过时间复杂度高,O(n^2),因为是直接两个loop
- 左右夹逼,小的一边往内收敛
Tips:
由于Golang好像没有Math.min max之类的官方工具包,所以只能自己实现
Code:
思路1(这里我这边提示超出时间限制,可能是时间复杂度太高了吧)
func maxArea(height []int) int {
var max int
for i:=0;i<len(height)-1;i++{
for t:=i+1;t<len(height);t++{
area:=(t-i)*min(height[t],height[i])
if(max<area){
max=area
}
}
}
return max
}
func min(a,b int) int {
if a<b{
return a
}else{
return b
}
}
思路2
func maxArea(height []int) int {
i,j:=0,len(height)-1
max:=0
for i<j{
cur:=(j-i)*min(height[i],height[j])
if(max<cur){
max=cur
}
if(height[i]<height[j]){
i++
}else{
j--
}
}
return max
}
func min(a,b int) int {
if a<b{
return a
}else{
return b
}
}