package main
import "fmt"
/*给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai)
在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
*/
func main() {
fmt.Println(maxArea1([]int{1, 8, 6, 2, 5, 4, 8, 3, 7}))
}
// 暴力遍历
func maxArea1(height []int) int {
n := len(height)
if n <= 1 {
return 0
}
maxMulti := 0
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
var h int
if height[i] >= height[j] {
h = height[j]
} else {
h = height[i]
}
w := h * (j - i)
if w > maxMulti {
maxMulti = w
}
}
}
return maxMulti
}
/*使用 2 个指针指向首部和尾部,将短指针向长指针方向移动,看能不能找到更长的线,使面积更大
依据:向长线方向每次移动 1 格,虽然宽度-1,但是(高度变高)*(宽度-1) >= 高度*宽度*/
func maxArea2(height []int) int {
max := 0
for i, j := 0, len(height)-1; i < j; {
var minHeight int
if height[i] <= height[j] {
minHeight = height[i]
i++
} else {
minHeight = height[j]
j--
}
w := (j - i + 1) * minHeight
if w > max {
max = w
}
}
return max
}