A: hi! ~ Hello, everyone, I am YK bacteria 🐷, a front-end microsystem ✨, like to share their small knowledge 🏹, welcome to follow me 😘 ~ [wechat account: YK2012YK2012, wechat official account: ykyk2012]

“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Simple topic heavy fist attack, medium topic I also do not take afraid of!! Today we’re going to do a medium problem, which is actually a very simple code, but this is an important idea.

11. Container with the most water (medium)

Leetcode-cn.com/problems/co…

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. The two endpoints of vertical line I are (I, ai) and (I, 0).

【 句 型 操 练

As soon as you get the problem, you don’t want to think about it, just double loop and enumerate all the results, and then return the maximum.

/ * * *@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++){
            let h = Math.min(height[i], height[j])
            let thisArea = (j - i) * h
            maxArea = Math.max(thisArea, maxArea)
        }
    }
    return maxArea
};
Copy the code

The result of course is timeout!!

A double pointer

The time complexity of the violent solution is O(N2)O(N^2)O(N2), which is obviously too inefficient. Think again, is it really necessary to enumerate all the cases by force?

So let’s think about what makes up the capacity of water in a container, which is base times height and base is the difference between two vertical lines, and height is the smallest of the two vertical lines. Let’s take two Pointers I and j, each pointing to two vertical lines, so if we want the container that holds the most water, it should be as far apart as possible from I and J, and the one whose I and J are smaller is not too small… A bit of a mouthful

So we can switch gears, we start with I and j directly at both ends of the array, and calculate how much water we can currently hold.

And then I have to move the pointer, which one do I move? Move the pointer with the smallest value inward.

Why do you do that? Let’s think of it this way, if you move the larger pointer, the smaller pointer will definitely determine the upper limit of the future height, and the distance between ij’s will get smaller, which means that the capacity will only go down, not up, and you won’t need to do anything to move the larger pointer.

So let’s summarize

Initially, two Pointers point to each end of the array to get the current capacity of water. Move the pointer one at a time, the pointer that points to the smaller value.

/ * * *@param {number[]} height
 * @return {number}* /
var maxArea = function(height) {
    let i = 0;
    let j = height.length - 1;
    let maxArea = 0;
    
    while(i<j){
        // Calculate the current capacity
        let thisArea = Math.min(height[i],height[j]) * (j - i);
        // Update the maximum capacity
        maxArea = Math.max(maxArea, thisArea);
        // Move the pointer
        if(height[i] <= height[j]){
            i++;
        }else{ j--; }}return maxArea;
};
Copy the code

Finally, we prove the correctness of our method by illustration

We throw away a lot of solutions when we move the pointer, but those are throwaway solutions that don’t affect the result

The search space for this problem is represented by a matrix that looks something like this.

If you iterate over all the solutions, you need order N^2 O N^2 O N^2

In this case, the search space is reduced by using the double pointer, which first yields the top right solution

Assume that column 0 on the left is shorter. I++ in the code; Corresponding to the search space, the search space of a row is reduced, as shown in the figure below.

Once we have eliminated one row from the search space, we look at the rest of the search space, which is still an inverted triangle.

The final GIF is shown here

Photo by Nettee; link

Finally, please pay attention to my column and make good friends with YK bacteria