Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Data structure and algorithm belong to the internal work of the developer, no matter how the front-end technology changes, how the framework updates, how the version iteration, it is the same content. Always remember in the byte youth training camp, moon shadow teacher said a word, do not ask front-end learning algorithm. Everyone in computer science needs to know about algorithms and has the subconscious to write high-quality code.

I. Problem description

Given an integer array height of length n. There are n perpendicular lines, and the two ends of the i-th line are (I, 0) and (I, height[I]).

Find the two lines that together with the X-axis will hold the most water.

Returns the maximum amount of water a container can hold.

Note: You cannot tilt the container.

Example 1:

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) is49.Copy the code

Example 2:

Enter: height = [1.1] output:1
Copy the code

Tip:

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

Ii. Explanation of ideas

  • The maximum amount of water is actually the problem of finding the area (height * width).

  • The maximum width is height.length-1

  • Constantly move the Pointers at both ends to find the maximum area. Each calculation is made by multiplying the width of one side of the short board to get the final area.

  • The point is, the needle on the short side needs to move. Until the two Pointers meet.

AC code

var maxArea = function(height) {
    let max = 0
    let i = 0 , j = height.length - 1
    while(i<j){
        let curRes = Math.min(height[i],height[j])*(j-i)
        max = curRes > max ? curRes : max
        if(height[i]<height[j]){
            i++
        }else{
            j--
        }
    }
    return max
};
Copy the code

Four,

Double-pointer type problems need to accumulate experience in doing problems. When meeting similar problems, pay attention to the words of the topic. Ontology requires maximum water storage, which naturally comes to iteration or dynamic planning. However, the core of this problem is that the boards at both ends will have the short board effect, and the final water storage will be related to the short board. There is a relationship between the length of the board, so it is easy to get the result of the problem by using the double pointer to iterate.

subsequent

  • Address: Find the median of two positive ordinal groups

Well, this article is about finding the median of two ordinal groups. My name is Shao Xiaobai, a junior student in the front end field, welcome to 👍 comments.