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.

实现：

package array;

public class MaxAreaDemo {

    public static void main(String[] args) {
        int[] heights = {1, 2, 2, 3, 4, 1, 2};
        System.out.println(getMaxArea(heights));
    }

    public static int getMaxArea(int[] heights) {
        if(heights == null || heights.length == 0) {
            return 0;
        }
        int left = 0;
        int right = heights.length -1;
        int max_area = 0;
        while(left < right) {
            max_area = Math.max(max_area, (right - left) * Math.min(heights[left], heights[right]));
            if(heights[left] < heights[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
}

 

def get_max_area(height):
    if not height:
        return 0
    max_area = 0
    left, right = 0, len(height) - 1
    while left < right:
        max_area = max(max_area, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

height = [1, 2, 2, 3, 4, 1, 2]
print get_max_area(height)

 贴一个有点差别的实现

def get_max_area(height):
    if not height:
        return 0
    max_area = 0
    left, right = 0, len(height) - 1
    while left < right:
        max_area = max(max_area, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            i = left
            while i < right and height[i] <= height[left]:
                i += 1
            left = i
        else:
            i = right
            while i > left and height[i] <= height[right]:
                i -= 1
            right = i
    return max_area

height = [1, 2, 2, 3, 4, 1, 2]
print get_max_area(height)