Problem
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, a_i). 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 and n is at least 2.
Solution
To clarify the problem, we are searching for the coordinates a_i
and a_j
for j>i, 0<i,j<n
such that the area (j-i)*min(a_i,a_j)
is maximized. The bruteforce solution is clearly O(n^2)
, and the problem cannot benefit from being sorted (since the solution depends on the original ordering). The trick to finding the optimal solution, which runs in O(n)
, is to recognize that as you reduce the width of the container by one, then either the lower height must increase, or both height must increase by one or more to have a larger area. Thus, starting with a_0
and a_n
, yielding the widest container, we can iterate on the side with the shorter height while maintaining the maximum area. If a larger container does exist, the height will have to be larger to make up for the smaller width, and so the side with the smaller height will iterate towards it. Trying a few examples can convince yourself that this is correct.
Time complexity: O(n)
Space complexity: O(n)
Runtime: 10 ms (63.17%)
1 2 3 4 5 6 7 8 9 10 11 12 | public int maxArea(int[] height) { int i=0, j=height.length-1, area=0; while (i<j) { area = Math.max(area, (j-i)*Math.min(height[i],height[j])); if (height[i] > height[j]) { j--; } else { i++; } } return area; } |
No comments:
Post a Comment