Container With Most Water - 每日算法

每日算法——letcode系列

问题 Container With Most Water

Difficulty: Medium

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

class Solution {public:    int maxArea(vector<int>& height) {}};

翻译

给定n个非负数整数a1, a2, ..., an, 每个数代表坐标(i, ai)的一个点。以(i, ai) 和 (i, 0)为线段的端点画了n条垂直的线。 找到其中两条， 使他们和x轴形成的一个容器可以装最多的水。

注意：容器不能倾斜。

思路

此题把求水的容量转换成求面积能好分析一点。

假设： 第i条和第j条(i < j)线和x轴围起来面积最大，那么最大面积为Sij = min(ai, aj) * (j - i);

那么：

• 在j的右边没有比他更高的线

• 在i的左边也没有比他更高的线

证明 ：
反证法：
如果在j的右边存在比他高的线为第k第线， 那么Sik = min(ai, ak) *(k - i)， 由于k > j，所以Sik > Sij，与Sij最大的条件矛盾。
同理可证在i的左边也没有比他更高的线。

从上面说的性质可以说明， 从头和尾分别向中间遍历a1, a2, ..., an, 如果遍历的线比前面的高，则更新当前最高，并算出面积与之前存的最大面积比较，当前更大则更新，否之则跳过。

但有一个问题： 头和尾哪个先向中间遍历呢？

高度矮的个。 因为如果高的向中间移动了，那矮的那边就不可能遍历到高的现在遍历的那个点了，就可能找不到最大面积。

这也是动态规划的用法。

代码

class Solution {public:    int maxArea(vector<int>& height) {        if (height.empty()){return 0;        }    int m = static_cast<int>(height.size());        int leftIndex = 0;        int rightIndex = m - 1;        int maxLeft = leftIndex;        int maxRight = rightIndex;        int maxArea = min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex);        while (leftIndex < rightIndex) {if (height[leftIndex] >  height[rightIndex]){    rightIndex--;    if (height[rightIndex] > height[maxRight] && leftIndex < rightIndex){        maxRight = rightIndex;    }}else{    leftIndex++;    if (height[leftIndex] > height[maxLeft] && leftIndex < rightIndex){        maxLeft = leftIndex;    }}int area = min(height[maxLeft], height[maxRight]) * (maxRight - maxLeft);if (maxArea < area){    maxArea = area;}        }        return maxArea;    }};