Collecting rain water (Question Number 42)

The title

Given n non-negative integers representing the height diagram of each column of width 1, calculate how much rain can be received by the columns arranged in this order after it rains.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] output: 6Copy the code

Example 2:

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

Tip:

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

link

Leetcode-cn.com/problems/tr…

explain

This one, this one is a little bit of a surprise.

You try to come up with a solution, and then look at the answer, good guy, there are actually 3 solutions, and simple and refreshing.

Because of the particularity of the situation, DP is not the optimal solution here, even the worst performance of the solution.

Let’s talk about their own solution, when I saw this problem, the first time I thought of the flooding algorithm, the whole table as a plane rectangular coordinate system of the first quadrant, divided into a unit of 1 lattice.

The bar graph has a value of 1, and the rest of the bar graph has a value of 0, and then you go through the entire two-dimensional array, and you add some conditions.

In fact, want to solve this problem, the key is to understand the relationship between the water grid and other grids, here do not sell officials, directly say 👇 :

The amount of water each lattice can receive depends largely on the lower of the tallest left and right pillars.

It may seem fancier to say so, but let’s take an example from the diagram above.

  • The first column

    There’s no room on the left side of this column, give up, can’t get water

  • The second column

    The highest cell on the left of this column is not its own height, so it can’t get water

  • The third column

    The height of the highest cell on the left is 1

    The height of the highest cell on the right is 2

    I’m going to take the lowest cell, which is the one on the left

    So all you have to do is compare the difference between the highest cell on the left and the current cell, so this is 1-0, and the water that you can connect to is 1 cell

  • The fourth column

    The highest cells on the left of this column are not their own height, so they can’t get water

  • The fifth column

    The highest cell on the left is 2

    The highest cell on the right is 3

    Take the minimum of both, 2

    Its height is 1, so the amount of water that can be connected to it is 1

  • The sixth column

    The highest cell on the left is 2

    The highest cell on the right is 3

    Take the minimum of both, 2

    Its height is 0, so the amount of water that can be connected to it is 2

  • The seventh column

    The water that can be connected to the fifth column is 1

  • The eighth column

    There’s no higher cell on the left. GG

  • The ninth column

    The highest cell on the left is 3

    There’s no highest cell on the right, or the highest cell is itself, GG

  • The tenth column

    The highest cell on the left is 2

    The highest cell on the right is 2

    Take the minimum of both, 2

    Its height is 1, so the amount of water that can be connected to it is 1

  • The eleventh column

    There’s no higher cell on the right. GG

  • The twelfth column

    Same as column 11, GG

So if you look at it this way, the answer is:

1 plus 1 plus 2 plus 1 plus 1 is 6Copy the code

So here we can get the key solution, to determine whether the ith lattice can receive water, first find the left and right higher lattice, notice the more word here, if the height is equal to itself can not receive water.

If you have a higher cell on the left and a higher cell on the left, take the minimum value of the two and subtract your height to find the amount of water that can be connected to the current cell.

The following three better methods are all attached to this key point, and if you don’t understand it, you may not understand the subsequent answer.

Your own answer (flood algorithm)

Function trapF(height) {var len = height.length Max = math.max (... For (let I = 0; let I = 0; i < max; Var start = false TMP = 0 // For (let j = 0; j < len; J++) {/* start counting if the switch is turned on the first time, TMP is 0, and res is unchanged. If the switch is turned on the second time, TMP has been accumulated in else, and res is added. If (height[j] > I) {start = true res += TMP TMP = 0} else {// If the switch is already on, TMP if (start) TMP ++}}} return res};Copy the code

There are some changes to the flooding algorithm, some optimizations.

We get rid of the two-dimensional array itself, because we don’t need to store data, we just need to accumulate the TMP variable.

First of all, you get the maximum value in the array, that’s the upper limit of this two-dimensional array, and that’s what you’re going to loop by.

And then you start to loop, you start to loop vertically, layer by layer, and then you loop horizontally through each layer, getting every element in this two-dimensional array.

Start is like a switch, and you can imagine having an array like this:

[0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0]Copy the code

Start is false at the beginning of the loop, so TMP does not add up. When the first 1 is encountered, start is true, and subsequent 0 elements are added to TMP. If it is 1, add the current TMP to the RES and reset TMP to start the next round of stacking.

This one is relatively simple, so I won’t repeat it here.

This answer is ok for the other same question, but it may not pass because the number of test cases is large.

The time complexity is O(n*m), where m is the largest number in the array.

The space complexity is order one.

Better Way (DP)

Universal DP ah, it is no problem to solve this problem.

The solution of DP is very simple and consists of three steps:

  1. Get the maximum left number into the array, that is, the maximum left height of the current element on each element
  2. Get the largest array on the right, same as 1
  3. Loop through the array to determine the relationship between the largest number on the left and the largest number on the right of the current element, and accumulate water.

👇 look at the code:

Function trapD(height) {var len = height.length leftMax = new Array(len) rightMax = new Array(len) res = 0 // LeftMax [0] = height[0] rightMax[len - 1] = height[len - 1] // Get the full leftMax for (let I = 1; i < len; {leftMax[I] = math. Max (leftMax[i-1], height[I])} // Obtain the full rightMax for (let I = len-2; i > -1; {rightMax[I] = math.max (rightMax[I + 1], height[I])} for (let I = 0; i < len; i++) { res += Math.min(leftMax[i], rightMax[i]) - height[i] } return res }Copy the code

The key idea is the same as explained in the explanation, but you need to pay attention to the leftMax and rightMax array initialization assignment, the other really nothing, very simple.

Time complexity O(n).

Space complexity O(n).

Better method (double pointer)

This is actually an enhanced version of the DP solution, because in the DP solution there are actually two new arrays to store the maximum number on the left and the maximum number on the right.

You can actually get rid of these two arrays, or you can get them dynamically.

So what’s the dynamic? In fact, when traversing to the current element, the maximum number on the left and the maximum number on the right are updated at the same time, and the amount of water is calculated.

If the maximum number on the left is small, then it takes a long time to compare the difference between the maximum number on the left and the current element on the left, take the water amount, and accumulate the answers.

If the maximum on the right is smaller, the same comparison is made.

👇 :

Function trapD(height) {var len = height. Length left = 0 Right = len - 1 leftMax = 0 rightMax = 0 res = 0 // While (left < right) {// update leftMax, rightMax leftMax = math.max (leftMax, rightMax); height[left]) rightMax = Math.max(rightMax, If (height[left] < height[right]) {res += leftmax-height [left] left++} else { // when res += rightmax-height [right] right--}} return res}Copy the code

Elements are positioned using the left and right variables, left starting from the far left and right starting from the far right. After the while loop, update leftMax and rightMax in real time, after the update, compare the size, and then value.

Better approach (monotonic stack)

Well, that’s okay, but the way you think about it, you might not think about it.

The core logic actually feels a little similar to the author’s flooding algorithm, here the main operation process is like this 👇 :

  1. First, make an empty array as the stack, and then start the loop.

  2. If there are no elements in the array, and the current element is no larger than the last element in the array, then insert the index of the current element directly into the array.

  3. If the current element is greater than the last element in the array, then extract the last element in the array, and if the array is empty after the extraction, then skip it.

  4. In the example above, the first formal operation starts at the fourth element of the loop, at which point the stack is [1, 2].

  5. So take the last element on the stack, the top element on the stack — 2.

  6. So to do the calculation, let’s first take the largest element on the left, which is the one at the bottom of the stack, which is 1. The largest element on the right, needless to say, is the current element, and its index is I

  7. The calculation here is done in blocks, first width, which is easy to calculate, i-left-1. The height calculation explains the core algorithm inside, the minimum value of the maximum height on both sides minus the height of the current element.

    The thing to notice here is that the current element is not I, it’s the top element that we pulled out before, which is 2.

    So the value of this step is 👇 :

    tmpWidth = i - left - 1
tmpHeight = Math.min(height[i], height[left]) - height[top]
res += tmpWidth * tmpHeight
Copy the code

    So we’re done, and we’re going to put the current I on the stack, and we’re going to do the rest of the loop.

    In this way, when the loop is complete it is the end.

The overall code 👇 :

Function trapS(height) {var len = height.length stack = [] res = 0; i < len; I++) {// if the current element is larger than the end of the stack, While (stack.length && height[I] > height[stack[stack.length - 1]]) {var top = stack.pop(); GG if (! Stack.length) break /* initialize the calculation variable to fetch the current stack end element, that is, the element to the left of the stack, for left to get the current width, for tmpWidth to get the current height, Height [top] = > I = > I = > I = > I = > I TmpHeight */ var left = stack[stack.length-1] tmpWidth = i-left-1 tmpHeight = math.min (height[I], Height [left]) -height [top] // calculate the value res += tmpWidth * tmpHeight} stack. Push (I)} return res}Copy the code

summary

Did not expect this simple one actually have so many solutions, is the next lost.

The key point is the understanding of the core ideas. In fact, these three solutions are based on the diffusion of the core ideas.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ