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.

	"""
	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.
	"""
	class Solution:
	# @return an integer
	def maxArea(self, height):
	if height==None or len(height)<2:
	return 0
	left=0
	right=len(height)-1
	maxArea=0
	while left<right:
	area=min(height[left], height[right])*(right-left)
	if maxArea<area:
	maxArea=area
	if height[left]<height[right]:
	left+=1
	else:
	right-=1
	return maxArea

view raw ContainerWithMostWater.py hosted with ❤ by GitHub

	/*
	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.
	*/
	public class Solution {
	public int maxArea(int[] height) {
	if (height==null || height.length<2){
	return 0;
	}
	int maxArea=0;
	int left=0;
	int right=height.length-1;
	// two pointers scan from two sides to middle
	while (left <right){
	int area=Math.min(height[left], height[right])*Math.abs(left-right);
	if (maxArea<area){
	maxArea=area;
	}
	// because the area is decide by the shorter edge
	// so only way to increase the area is to increase the
	// shorter edge
	if (height[left]<height[right]){
	left++;
	}
	else{
	right--;
	}
	}
	return maxArea;
	}
	}

view raw ContainerWithMostWater.java hosted with ❤ by GitHub