Container With Most Water, Leetcode 解题笔记

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.

这道题的关键是理解题意,因为题目的描述容易让人产生歧义,按照描述,需要在所有上述垂线中找到两条使得它们与x轴构成的容器容积最大,此处注意,题目本意是要忽略两条垂线之间的其他垂线。有一道类似的题目是用立柱来替换垂线,后面我们应该会遇到。

稍加分析,此题其实是要计算(任意两条直线中较短的线的长度*此两条线之间的宽度)的最大值。

最直观的方法当然是暴力解法,两轮遍历,复杂的O(n^2)。但是如果只有暴力解法就没必要列入leetcode了,此处应考虑从两头向中间找,如果左线比右线低,则左线向右移;如右线低,则右线向左移。这样直到两线相遇,可以确保我们找到最大值,并且复杂度只有O(n)。

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

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