leetcode-题解-盛最多水的容器（数学证明双指针法）

￡神魔★判官ぃ 2023-01-18 02:22 108阅读 0赞

题目：https://leetcode-cn.com/problems/container-with-most-water/

> 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/container-with-most-water  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
解：  
设x轴的范围为\[0, n\], 设i初始值为0，j初始值为n，故问题 转为求 x在\[i, j\]范围内 盛最多水的问题，记作MaxP(i,j)，进行下面的判断

1.1）若Yi <= Yj, 则area(1) = (j - i) \* Yi。  
假设最终结果为(i, d)2个位置 盛水最多，则area = min(Yi, Yd) \* (d - i) <= Yi \* (d - i)  
又知道 d 范围 \[i, j\], 即 d <= j, 故area <= area(1)。

即若最终结果包含i位置，则其最值必然为area1，因此最初的问题 可转为 max(除i外的最大值, area(1))，  
即max(MaxP(i+1, j), area(1))的问题。

2）若Yi > Yj, 则area(1) = (j - i) \* Yj。  
同理问题MaxP(i, j) 可转化为 max( MaxP(i, j-1), area(1))的问题。  
即将规模n + 1的问题，将为了n的问题

2.若i != j, 循环继续1）、2）步骤，最终将问题降为规模为1的问题，

最终可知MaxP(i, j) = max(area(1), area(2), area(3),…, area(N))的问题, 即数列area(x)的最大值问题。

算法步骤相当于：  
设i = 0，j = n, res = 0;  
1）res = max(res, (j-i) \* min(Yi, Yj)), 若Yi <= Yj, i++, 否则j–；  
2）若i != j，继续1）；  
3）返回结果res。

public int maxArea(int[] height) {
            int i = 0;
            int j = height.length - 1;
            int max = 0;
            while (i < j) {
                int area = j - i;
                area *= height[i] <= height[j] ? height[i++] : height[j--];
                if (max < area) {
                    max = area;
                }
            }
            return max;
        }