Title: Container With Most Water Source: leetcode.com
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.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
/*https://leetcode.com/problems/container-with-most-water/*/ public class ContainerWithMostWater { public static void main(String args[]) { ContainerWithMostWater c = new ContainerWithMostWater(); int[] height = {4, 3 , 2, 1}; System.out.println(c.maxArea(height)); } public int maxArea(int[] height) { int p1 = 0; int p2 = height.length-1; int maxArea = 0; while(p1<p2) { int area = (p2-p1) * Math.min(height[p1], height[p2]); if(area > maxArea) maxArea = area; if(height[p1]<=height[p2]) p1++; else if(height[p2]<height[p1]) p2--; } return maxArea; } } |