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

42. Catch rain water

This brush topic diary 14, force deduction is: 42. Receive rain, difficult

I. Title Description:

At first glance, the problem expression is also very simple and clear, but it is a difficult problem

Is it possible that the fewer statements a problem has, the more difficult it is? 11. It looks like these two problems are similar. I’m sure we can solve them

Ii. Analysis of Ideas:

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

It doesn’t matter big brother, we can solve any problem, even if we can’t solve it for a while, we can also study, ask others for advice, we can always solve it in the end, believe in yourself

It is the same in work, correct attitude, encounter problems, think more about the logic and principle behind, and try to solve all the same type of problems in the future

Let’s start by looking at what this question tells us that is important:

• First, this is a difficult question, we should try our best to consider all aspects, do not have the heart pressure
• Second, this is also a matter of calculating volume. The containers that hold the most water are a little different, but depending on whether they can hold rain, it’s still a short game
• And here we have to notice that they’re giving us the length of the array in the range of 1 to 10 to the fourth power

Is that how we think about counting rain?

Traverse from left to right, calculating the height difference when the right side is higher than the left, then subtracting the column height in the process

However, it was found that such pure logic was problematic, because the columns on the right were not always high on the left, and vice versa. It was found that in the figure above, it was impossible to go according to pure logic, and there might be scenes and logic in the middle that we had not considered properly

So let’s think about it, if we could directly figure out how many units of rain a particular row could receive, wouldn’t that make it a little bit clearer?

How do you calculate how much rain the current row can hold?

Again, how much water a bucket can hold depends on the short board, so whether the current column can receive rain, how much rain can receive, also depends on whether the current column is shorter than the left and the right

Then, we can see the following illustration

By looking at the illustration above, we know how much rain the current column can absorb. We just need to calculate the height of the current column on the left and the height of the current column, and then subtract the height of the current column

So, let’s implement this idea briefly, and the logic is clear, to calculate the amount of rain that follows by column, and then sum over all the columns

Three, coding

Based on the above logic and analysis, we can translate it into the following code

The encoding is as follows:

func trap(height []int) int {
    // Calculate the maximum height to the left of each column
    leftMax := make([]int, length)
    leftMax[0] = height[0]
    for i:=1; i< length- 1; i++ {
        leftMax[i] = max(leftMax[i- 1], height[i])
    }
    // Calculate the maximum height to the right of each column
    rightMax := make([]int, length)
    rightMax[length- 1] = height[length- 1]
    for i:=length - 2; i>= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    // Calculate the actual number of rain units in the current column
    res := 0
    for i,h := range height {
       tmp := min(leftMax[i],rightMax[i])
       if tmp > h{
           // Only when the current column is short, can it receive rain water
            res += tmp - h
       }
    }
    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:

This problem is O(n) in both time and space, because we only need to traverse the height array once, and we introduce O(n) level space consumption

42. Catch rainwater

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 ~