Leetcode 11. 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.

原题链接：Container With Most Water

　　题目可以这么理解，在i位置有条高为ai的竖线，让你选出两台竖线构成一个容器，使得该容器装的水最多，注意容器不能倾斜。

          |
  |       |
  |       |    
  |   |   | |     |
| |   |   | | |   |
| | | | | | | | | | | 
0 1 2 3 4 5 6 7 8 9 10 

　　如上图，横纵都为一个单位，我们很容易看出来1和9位置组成的容器容积最大，所盛水为24个单位。大家都知道桶的容积是有最短的一条木板决定的，在这副二维图中是由短的一条边决定的。
　　 没有什么问题是通过暴力解决不了的，这道题也是，我们直接暴力选取两条边，算最大容积就好了，时间复杂度O(n^2)。 显然，这并不是最优解，其实还有O(n)的解法。
　　我们用两个指针l和r分别从两头往中间移动，直到重合，记录下移动过程中最大的容积。 移动的策略是如果height[l] < height[r] l右移，反之r左移。 代码很简单，但是很难理解，为啥这样就算出正确答案了？？
　　想想看，容器的容积是有最短的一条边决定的，l和r如果你把长边向中间移动的话，容积只会减少不会增加，对不，所以移动长边是无意义的。但是移动短边，有可能短边会变长，容积可能变大。不知道我说清楚了吗，反正这就是大体的思路，很明显这是O(n)的时间复杂度。

代码如下：

public class Solution {
    public int maxArea(int[] height) {
        if (height.length < 2) return 0;
        int ans = 0;
        int l = 0;
        int r = height.length - 1;
        while (l < r) {
            int tmp = (r - l) * Math.min(height[l], height[r]);
            if (v > ans) 
                ans = tmp;
            if (height[l] < height[r]) 
                l++;
            else r--;
        }
        return ans;
    }
}

~谢谢打赏~

赏