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

11. Container that holds the most water

11. The container that holds the most water, medium

I. Title Description:

How did it feel to get this problem?

Calculate the maximum amount of water a container can hold. However, the more specific the description, the more confusing it will be.

It’s okay, guys. Let’s just play. Analyze it

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

Let’s take a look at what the question tells us:

  • They’re going to give you an array, and the number of elements is 2 to 10 to the fifth, which means that we don’t have to determine if the size of the array is less than 2
  • Turn the array into a container, calculate the width and height, and figure out how much water the container can hold

It’s kind of like the bucket effect, where how much water a bucket can hold depends on the shortest board, and how much water the container can hold depends on two variables

  • Height of container
  • Container width

The overall need is to maximize the height of the container * width of the container

So let’s deduce:

[1,8,6,2,5,4,8,3,7]

For this problem, we want to calculate the maximum size of the container to hold water, so we can use a box to choose, would you like to box? Expand the box from left to right

Expand to the right based on the first column

Skip the next steps…

Take the second column and expand to the right

Skip the next steps…

According to the above way, it is true that we can find the maximum amount of water we expect to find, but this way of time complexity is too high, inevitably time out, we can change the idea

Since we want to find the maximum amount of water, shouldn’t we start with the largest possible data boundary? We can’t control the height of the column, but we can control the width of the container

So we can do it this way

  • Directly from the leftmost column and the rightmost column serve as the boundary of the container to continuously close in the middle
  • When it comes time to fold, start with the shorter side so it’s easier to understand and we can reduce the number of loops

The figure above has explicitly simulated the boundary closing process, so what remains is for us to implement the above idea together, using the two-pointer method

Three, coding

We do not need to determine whether the length of the given array is less than 2

The encoding is as follows:

func maxArea(height []int) int {
	// Assign an initial value to the left and right boundaries of the container (double-pointer method)
    i , j := 0.len(height) - 1

    res := 0
    for i<j {
        // Calculate the container area of the current boundary, depending on the shorter side
        res = max(res,(j-i) * min(height[i],height[j]))
		// Start from the shorter side
        if height[i] < height[j]{
            i++
        }else{
            j--
        }
    }
    return res
}

func max(a,b int)int{
    if a>b {
        return a
    }
    return b
}

func min(a,b int)int{
    if a<b {
        return a
    }
    return b
}
Copy the code

The above is the code according to the idea, the idea is clear, coding is a translation process, consider all kinds of scenarios, we can achieve more smoothly, can reduce the risk of rework and bugs

Iv. Summary:

We only need to traverse the entire array once, so the time is O(n), and the space is O(1), because we’re consuming constant space

The container that holds the most water

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~