博文中会简要介绍Leetcode P0011题目分析及解题思路。

“Container With Most Water”是一道比较经典的题目的简化版，这题考察的核心主要在于优化时间复杂度、对双指针的判断及指定合理的约束条件。

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 and n is at least 2.

这道题比较容易想到的暴力解法是两两配对，这样以来时间复杂度是O(n^2)。显然这样的时间复杂度是不会符合要求的，所以一定存在明显的优化，容易想到的是将时间复杂度降低为线性的。

按题目中的描述，约束一个容器的条件是容器两端的高度，此时关注到的重点是“两端”，也就是说想要优化成线性时间复杂度，可以考虑使用双指针来规定容器两端的位置，然后双指针相向而行，当指针重合，即结束扫描，且这样以来时间复杂度就是线性的。

然后关注到的是高度，一个容器的储水能力在于短板，比方说，左端高度始终低于右端时，无论左端如何移动，最终的储水能力都取决于左端高度，所以这个时候需要移动的是左端指针，来寻找最大存储容器。那么什么时候需要移动右端呢？当左端高度大于右端高度时，开始移动右端，因为当前的容器储水能力将取决于右端的高度。

综上，我们便可以得到双指针移动的约束条件，然后再通过一个变量来记录最大值，即可以在线性时间内得到最值解。

以下是Java的题解代码实现。

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        
        int left = 0, right = height.length-1;
        int maxVol = Math.min(height[left], height[right])*(right-left);
        while (left < right) {
            int vol = Math.min(height[left], height[right])*(right-left);
            maxVol = Math.max(maxVol, vol);
            if (height[left] < height[right]) {
                ++left;
            }
            else {
                --right;
            }
        }
        
        return maxVol;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int maxArea(vector<int>& height) {
        if (height.size() == 0) 
            return 0;
        
        int max_vol = 0;
        int left = 0, right = height.size()-1;
        while (left < right) {
            int vol = min(height[left], height[right])*(right-left);
            max_vol = max(max_vol, vol);
            
            if (height[left] > height[right]) {
                --right;
            }
            else {
                ++left;
            }
        }
        
        return max_vol;
    }
};