Problem
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.
Solution
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
var max = 0;
var l = 0;
var r = height.length - 1;
while (l < r) {
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return max;
};
Explain:
双指针从两头开始,判断哪边更高。积水量是矮的那边决定的,移动高的那边不可能提升积水量,所以移动矮的那边。
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).