题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1] 输出：1

提示：

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

解题思路

把最外侧的两根线作为候选容器（左右指针），计算容积后：每一步把高度较小的那一侧指针向内移动一格，因为只有移动较矮的一侧才有机会增加容器的“高度”（从而可能增加面积）。重复直到两个指针相遇，过程中记录最大面积。

设左右指针为 i（左）和 j（右），当前容积为：

area = (j - i) * min(height[i], height[j])

• 容量受两者中较短的那根限制（短板效应）。
• 若 height[i] < height[j]，当前水面高度就是 height[i]。把右指针 j 向左移动，宽度变小了，而水面高度最多变到 height[j]（右边高），但高度仍 ≤ height[j]。即使右侧再高，也无法让当前由左侧短板限制的高度变高 —— 因此当前若想超越已有面积，只能通过把左指针向内找一根比 height[i] 更高的线来实现（因为只有这样水面高度的下限才可能提升）。所以我们移动较矮的一端（左端）来寻找更高的短板。

（对称地，如果 height[j] < height[i]，就移动右指针。）

具体代码

func maxArea(height []int) int {

    left := 0
    right := len(height) - 1
    Area := 0
    maxArea := 0

    Max := func(a, b int) int {
        if a < b {
            return b
        } else {
            return a
        }
    }

    Min := func(a, b int) int {
        if a < b {
            return a
        } else {
            return b
        }
    }

    for left != right {
        Area = Min(height[left], height[right]) * (right - left)
        maxArea = Max(maxArea, Area)
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
    
}