preface

Wrote an article this morning [LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch article brush. In order to be able to use the most simple and clear words to express, is really every sentence to think about the meaning of the right, reasonable is not reasonable, so write slowly, but also can make their own more clear understanding, just saw the nuggets of little sister hair advice decided to write a 😊! If you think it’s good, just like ❤️

Topic describes

This is LeetCode11 — the container that holds the most water on medium difficulty.

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 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: height = [1,1Copy the code

Example 3:

Input: height = [4,3,2,1,4Copy the code

Example 4:

Input: height = [1,2,1Copy the code

Tip:

  • n = height.length
  • 2 <= n <= 3 * 10^4
  • 0 <= height[i] <= 3 * 10^4

Their thinking

Given an array height, the size of the container that can hold the most water is determined by the shortest board. Left =0, right=height.length-1.

Take the data from Example 1 as an example:

The two Pointers point to the left and right sides of the array, and math.min (1, 7) * (right-left) = 8.

Min (8, 7) * (right-left) = 49.

At this time we can get:

 res1 = Math.min(height[left], height[right]) * (right - left);
Copy the code

Then take the maximum water amount compared with the amount obtained last time, namely:

res = Math.max(res, res1); Math. Max (res, math. min(height[left], height[right]) * (right-left));Copy the code

This time the solution of this problem is not very clear and clear! Start writing the solution code!

The problem solving code

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

conclusion

This problem is a classic double pointer problem, we meet such a problem do not be afraid, must smile in the face of it, write over.

Go HXDM!!

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