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.

首先,装的水的量是由两条竖线之中最小的一个和两个竖线之间的距离决定的,假设两块板的横坐标是i和j的话,他们装水的量就是min(height[i], height[j])*(j – i).
想到的第一个方法是将两两之间所有的面积都算一遍取最大值,那样就是O(n^2)的时间
另外在网上看到一个O(n)的解法,具体的代码很简洁,解法如下
一个pointer i从0开始,另一个j从尾部开始,
如果height[i] < height[j],i++,反之j–, 同时记录下当前的装水量,如果超过max就overwrite max。
其思想是如果height[i] < height[j]的话,那么当前的装水量就已经是以i为左边的所有container中最大的装水量了,同理j也是一样,因为装水量只取决于最短的那条边和底边。

public class Solution {
    public int maxArea(int[] height) {
        int i = 0; 
        int j = height.length - 1;
        int max = 0;
        while(i != j)
        {
            if (height[i] < height[j])
            {
                if (height[i] * (j-i) > max)
                    max = height[i] * (j-i);
                i++;
            }
            else
            {
                if (height[j] * (j-i) > max)
                    max = height[j] * (j-i);
                j--;
            }
        }
        return max;
    }
}

Second Submission, simpler code

public class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length-1;
        int max = Integer.MIN_VALUE;
        while(l!=r) {
            max = Math.max(max, Math.min(height[l], height[r])*(r-l));
            if (height[l] < height[r]) {
                l++;
            }
            else {
                r--;
            }
        }
        return max;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s