11. Container With Most Water

Difficulty:
Related Topics:
Similar Questions:

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: