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.
左右两个指针夹逼准则。如果left < right,先记录当前area,left++,反之则right--。因为如果left小的话,如果我们移右指针,结果总比当前area小。
public class Solution { //Time: O(n) Space: O(1) public int maxArea(int[] height) { if (height == null || height.length <= 1) { return 0; } int left = 0; int right = height.length - 1; int area = 0; while (left < right) { int h = Math.min(height[left], height[right]); area = Math.max(area, h * (right - left)); if (height[left] == h) { left++; } else { right--; } } return area; } }
No comments:
Post a Comment