LeetCode100 11. 盛最多水的容器

从两遍向中间遍历

水桶在越来越窄的情况下只有换短板才有可能通过增加高度从而增加盛水量。

假设左矮右高：面积由左边短板决定。如果移动右指针，宽度变小，短板还是左边，面积一定不会更大；只有移动短板，才有可能找到更高的挡板，面积变大。

class Solution {
public int maxArea(int[] height) {
int l = 0;
int r = height.length – 1;
int maxVolume = 0;

while (l != r) {
// 面积 = 两根柱子较矮的高度 × 两根柱子之间的距离
maxVolume = Math.max(maxVolume, Math.min(height[l], height[r]) * (r – l));
// 移动较矮一侧的指针（短板决定高度，移动高板面积只会更小）
if (height[l] <= height[r]) {
l++; // 左矮，右移左指针，试图找到更高的左板
} else {
r–; // 右矮，左移右指针，试图找到更高的右板
}
}
return maxVolume;
}
}

时间复杂度：O(N)，双指针总计最多遍历整个数组一次。

空间复杂度：O(1)