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 and n is at least 2.
思路: two pointers
两根指针,分别指向头尾,若height[i] < height[j], 则i++, 否则j--. O(n)时间复杂度。
原理: 木桶原理的特点是取短板。 因为水的最大高度只能到短板,否则会溢出。
为什么height[i] < height[j],i++?
证明: 反证法。
假定height[i] < height[j], 取任意k, 使得 i < k < j。
=> (j - i) * height[i] > (k - i) * min(height[i], height[k])
= > 移动j指针,只会得到比当前更小的容量。 因为 (j - i) >> (k - i), height[i] >= min(height[i], height[k])
=> 因此,若移动i,则有可能得到比当前更大的容量。
public class Solution { public int maxArea(int[] height) { if(height == null || height.length < 2) { return 0; } int i = 0; int j = height.length - 1; int max = 0; while(i < j) { if(height[i] < height[j]) { int tmp = (j - i) * height[i]; max = Math.max(max,tmp); i++; } else { int tmp = (j - i) * height[j]; max = Math.max(max,tmp); j--; } } return max; } }