题目描述:
给定一个长度为
n的整数数组height。有n条垂线,第i条线的两个端点是(i, 0)和(i, height[i])。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。
分析:
如果确定了两个边界,那么水的容量就是容器宽度 * 短板的高度
如果用指针 i和 j表示桶的两个边界,那么需要考虑的情形如下所示(白色部分):

最开始的时候,i = 0, j = 7
这个时候应该容器的宽度是 7,水面的高度为 3
- 如果移动比较长的那一块板,那么水面的高度一定不会超过
3; - 如果移动比较短的那一块板,那么水面的高度可能升高,也可能降低
由于 i = 0, j = 1~7的情况都是水更少的情况,所有可以排除这些情况
也就是移动短的木板,使得 i = 1, j = 7
排除了一定会使得水更少的情况,新的搜索空间如图:

