题目描述:
给定一个长度为
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
排除了一定会使得水更少的情况,新的搜索空间如图: