题目描述:

    给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 image.png

    分析:
    如果确定了两个边界,那么水的容量就是容器宽度 * 短板的高度

    如果用指针 ij表示桶的两个边界,那么需要考虑的情形如下所示(白色部分):
    image.pngimage.png

    最开始的时候,i = 0, j = 7
    这个时候应该容器的宽度是 7,水面的高度为 3

    • 如果移动比较长的那一块板,那么水面的高度一定不会超过 3
    • 如果移动比较短的那一块板,那么水面的高度可能升高,也可能降低

    由于 i = 0, j = 1~7的情况都是水更少的情况,所有可以排除这些情况
    也就是移动短的木板,使得 i = 1, j = 7
    排除了一定会使得水更少的情况,新的搜索空间如图:
    image.png

    参考:https://leetcode-cn.com/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/