Featured image of post Container With Most Water

Container With Most Water

11. Container With Most Water

分析

用两个指针i和j分别指向开头和结尾,如果指针i指向的水柱高度较低,则指针i向后移,反之指针j向前移。每移动一次后,求当前指针i和j指向水柱之间的面积,更新一下最大值。

为什么更新出来的值一定是最优解。 i和j最开始在两侧,每次把一个指针向中间靠拢,则一定有一侧指针会先到最优解的位置。假定指针i先到最优解位置,则指针j一定在其最优解位置的右边,并且指针j在到达最优解位置前每次指向的水柱高度严格小于最优解位置的高度。

可以使用反证法证明。如果指针j当前指向的水柱高度大于等于其最优解位置的高度,则能装的水量一定大于最优解,就和最优解位置矛盾。因此,通过上述过程,一定可以遍历出最优解。

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        for (int i = 0, j = height.size() - 1; i < j; ) {
            res = max(res, min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) i ++ ;
            else j -- ;
        }
        return res;
    }
};
Built with Hugo
Theme Stack designed by Jimmy