Topic describes

11. Container that holds the most water (medium)

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: You cannot tilt the container

Example:

Input:1.8.6.2.5.4.8.3.7] output:49Explanation: The vertical lines represent the input array [1.8.6.2.5.4.8.3.7]. In this case, the maximum amount of water the container can hold (shown in blue) is49Enter: height = [1.1] output:1Enter: height = [4.3.2.1.4] output:16Enter: height = [1.2.1] output:2
};
Copy the code

Tip:

  • n = height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104

Thought analysis

Double pointer, shrinking to the middle. To make sure we get the maximum, we just move the shorter side as we shrink to the middle and keep the maximum on the way.

Time is order n.

Space complexity is O(1).

var maxArea = function (height) {
  let left = 0, right = height.length - 1, maxArea = 0;
  while (left < right) {
    let currentWidth = right - left,
      currentHeight = Math.min(height[left], height[right]);
    maxArea = Math.max(maxArea, currentWidth * currentHeight);
    if (currentHeight === height[left]) {
      left++;
    }
    else{ right--; }}return maxArea;
};
Copy the code

To summarize

Let’s use JavaScript to brush algorithms: LeetCode-JavaScript

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign