11. Container With Most Water 能装

题目

给定一个长度为 n 的数组 height。有 n 条直线其断点是 (i,0) (i, height[i])。
找到两个直线，这两条直线和 x 轴组成容器能乘最多的水。也就是面积最大。

解析

1. 我们将游标置于两端，i，j 其面积为 (j-i)min(height[i],height[j])
2. 对于 i 和 j 来说，可能的更大值可能以高边为界限的，不可能以低边为界限
3. 如果 i == j，说明可能的更大值绝对不会以任意一条边为边界。

代码

伪代码

rst = 0
for ; i<j;
  rst = max(rst,(j-i)*min(height[i], height[j])
  if height[i] <= height[j]
    i++
  if height[i] >= height[j]
    j--
}

这个伪代码有问题，当第一次判断 i++ 之后，第二次判断 i 已经变了。为了简化代码造成逻辑错误！！！

只是为了说明，如果两数相等的情况，可以直接移动两个指针。

func maxArea(height []int) int {
    rst := 0
    i:=0
    j:=len(height)-1
    for ; i<j; {
        rst = max(rst, (j-i)*min(height[i], height[j]))
        if height[i] < height [j] {
            i++
        }else {
            j--
        }
    }
    return rst
}

func max(a int, b int) int {
    if a < b {
        return b
    }
    return a
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}