Give you n non-negative integers A1, A2, A3… 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.

Example 1

,8,6,2,5,4,8,3,7 input: [1] output: 49 explanation: the figure in the vertical line represents the input array,8,6,2,5,4,8,3,7 [1]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.Copy the code

Example 2

Input: [1,1] output: 2Copy the code

Example 3

Input: [4,3,2,1,4] output: 16Copy the code

prompt

  • N = array length
  • 2 <= n <= 
    1 0 5 10^5
  • 0 <= array [I] <= 10410^4104

The topic mainly investigates the array traversal combination. It is easy to think of the method is to find the area of the array items I and J in pairs, and step by step traversal to find the maximum area value. One of the things to notice is that the y value of the area is the smaller of the two terms. Code v1:

/** * find the area of the array items I and j, and step by step traversal, @param {number[]} height * @return {number} */ var maxArea = function(height) {let maxArea = 0 for (let i = 0; i < height.length - 1; i++) { for (let j = i + 1; j < height.length; J ++) {// height[I], height[j] Sheng water calculate by minimum baffle const x = j - I, y = math.h min (height [I], height [j]) const tempArea = x * y maxArea = math.h Max (maxArea, Console. log(maxArea([1,8,6,2,5,4,8,3,7]))Copy the code

V1 version of the time complexity is O(N²), to consider how to reduce the number of traversal, we can use the second traversal length from N to N /2, code v2:

/** * use the bidirectional pointer to reduce the number of iterations of the second loop. Time complexity becomes O(N²/2) * @param {number[]} height * @return {number} */ var maxArea = function(height) {const N = height.length  let maxArea = 0 for (let i = 0; i < n - 1; i++) { for (let j = i + 1, k = n - 1; j <= k; j++, k--) { const area1 = (j - i) * Math.min(height[i], height[j]) const area2 = (k - i) * Math.min(height[i], Height [k]) maxArea = math. Max (maxArea, area1, area2)}} return maxArea} console.log(maxArea([2,3,4,5,18,17,6])Copy the code

The time complexity of v2 version is reduced to O(N²/2). Based on this version, can Lenovo use square double pointer for both layer cycles, so that the time complexity can be further reduced by half O(N²/4), code V3:

/** ** Time complexity reduced to O(N²/4) * @param {number[]} height * @return {number} */ var maxArea = function(height) {const N = height.length let maxArea = 0 for (let i = 0, j = n - 2; i <= j; i++, j--) { for (let k = i + 1, l = n - 1; k <= l; k++, l--) { const area1 = (k - i) * Math.min(height[i], height[k]) const area2 = (l - i) * Math.min(height[l], height[i]) maxArea = Math.max(maxArea, area1, area2) if (j < l) { const area3 = (l - j) * Math.min(height[l], Height [j]) maxArea = math.max (maxArea, area3)}}} return maxArea} console.log(maxArea([2,3,4,5,18,17,6]))Copy the code

V1, V2, v3 are actually using the violent solution, but relatively reduce the number of traversal, is there only traversal once to achieve the same effect? Consider discarding unnecessary comparisons as you traverse.

A layer of circular bidirectional pointer can be used to traverse from both sides of I = 0 and j = n-1 inward. It is assumed that the area enclosed on both sides of the sink is S(I, j), and H [I] and H [j] are the heights of both sides of the sink respectively.

For example, h[0] > H [8] in the current state of I =0, j = 8 and S(0, 8), there are two methods of pointer shift. if

  • Move high: discard S(0, 1), S(0, 2),… , S(0, 7), but the area of S(0, 6) may be greater than S(0, 8), so this shift method is not feasible.
  • Move short: discard S(1, 8), S(2, 8)… , S(7, 8), where the area will definitely not be larger than S(0, 8), because the width j-i is smaller, but the height will not exceed H [8]. Therefore, this kind of movement method can effectively reduce unnecessary traversal.

The specific implementation code is as follows: the time complexity is reduced to O(N), and the space complexity is O(1).

/** * single-layer double-pointer loop, from outside to inside, * @param {number[]} height * @return {number} */ var maxArea = function(height) {const n = height.length let maxArea = 0, i = 0, j = n - 1 while(i < j) { maxArea = Math.max(maxArea, (j - i) * Math.min(height[i], If (height[I] < height[j]) {I ++} else {j--}} return maxArea} console.log(maxArea([2,3,4,5,18,17,6]))Copy the code