盛水容器问题

Posted on Edited on In Word count in article: 586 Reading time ≈ 1 mins.
计算可以盛最多的水，即最大面积

问题

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。
1

方法

设两个坐标a,b,分别从列表的起始端和结束端向中间移动，起始面积为0，每移动一次，即得到新的面积，与上一次移动的面积进行比较，取最大值，移动到ab相等时结束移动，如果a板高于b板，则以b板算面积，算完进行比较然后，缩减b的长度，a板小于b板，则以a板算面积，进行比较，增加a。最后a>=b跳出循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxArea(height []int) int {
    a, b, res := 0, len(height)-1, 0
    for {
        if a >= b {
            break
        }
        if height[a] > height[b]{
            if  height[b]*(b-a) > res {
                res = height[b]*(b-a)
            }
            b--
        } else {
            if  height[a]*(b-a) > res {
                res = height[a]*(b-a)
            }
            a++
        }
    }
    return res
}