11. Container With Most Water

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).