题目描述

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

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

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

说明：你不能倾斜容器。

题目分析

容器的容积由宽和高两部分组成，宽度是两条线横坐标的差，高度是两条线高度的最小值。
寻找最大水量，也就是宽度和高度都要尽可能的大。对于题目给出的数据，不同高度之间并不连续，而宽度是连续的，因此考虑从宽度入手。
使用双指针，left 指向数组最左边，right 指向数组最右边，此时宽度是最大的。
– 移动高度较小的指针：新的容积可能会变大，也可能会变小
– 移动高度较大的指针：无论移动多少次，新的容积都不可能变大

因此对于此刻高度较小的线，后续都没必要作为边界了，可以把它删除了，相邻的线成为新的边界（由于原来的线是数组的最左侧或最右侧，因此只有一个相邻的线）。
体现在代码上就是每次移动高度较小的指针，且指针只允许向内移动。如果两个指针高度相同，则移动哪个都一样。

Java

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int ans = 0;
    while (left < right) {
        int w = right - left;
        int h = Math.min(height[left], height[right]);
        int size = w * h;
        ans = Math.max(ans, size);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return ans;
}

Kotlin

fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var ans = 0
    while (left < right) {
        val size = min(height[left], height[right]) * (right - left)
        ans = max(ans, size)
        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }
    return ans
}