After the rain
What I’m going to bring you today is a very, very, very classic problem called the rain problem, which is a problem that many algorithm books give examples of. Although it is difficult, but relatively easy to understand, the length of the code is moderate, said so many, just one meaning, you remember the topic ah, really is a very nice question, let’s look at the description of the topic.
Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.
Example 1:
Enter: height = [0,1,0,2,1,0,1,3,2,1,2,1,2,1]
Output: 6
Copy the codeExample 2:
Enter: height = [4,2,0,3,2,5]
Output: 9
Copy the codeExample 3:
Input:,3,2,0,1,1,5 [4]
Output: 13
Copy the codeThe height diagram above is represented by the array [4,3,2,0,1,1,5], in which case 13 units of rain can be caught (see figure below).
What is the meaning of the passage?
For those of you who have just started to brush the above examples, let’s combine the pictures to understand. Let’s use example 3 to illustrate what the rain represents.
The picture above is the description of our title, do you understand? You can also think of it this way: we put yellow boxes on the ground at several heights, and they have gaps between them, and we want to insert blue boxes into them, and make sure that the left view and the right view of those boxes cannot see the blue box.
So now that we know what the problem is, let’s see how we can solve it. And before we do that, we can take a look at another problem that we did before: daily temperature. The idea behind these two questions is similar, both using the idea of a monotonous stack. Let’s look at the specific idea.
Here we also said the drab stack in the system, monotonous stack meaning is the element in the stack is drab, we used the two topics are decreasing stack (also can be the same), we, in turn, to press the elements into the stack, if the current element element is less than or equal to stack into the stack, if the element is greater than the stack is constantly out of the stack will stack first, until it is less than or equal to the current element stack elements, The current element is then pushed onto the stack. For example, if you want to push 4, you need 2,3 to push it, because 4 is bigger than both of them.
We know the meaning of monotone stack. Now let’s take a look at how to do the rain problem. In fact, the principle is very simple, we use our example 3 to illustrate.
First we’re going to push 4,3,2,0 the first four elements of our array are monotonic. But our fifth 1 is greater than 0. So we need 0 out of the stack and 1 in the stack. But why are we doing this? What’s the point? Don’t worry. Let’s look at the picture below.
Above, our 4,3,2,0 is already on the stack, our other element is 1, the element at the top of the stack is 0, and the element at the top of the stack is 2. So what about the amount of rain we get at this level? 2, 0, and 1 can catch water in one unit (see figure below). This is the amount of water we can catch in the first layer.
Note: if you can get water, it must be low in the middle and high on both sides.
Because we need to maintain a monotonic stack, we need to push 0 off the stack and 1 onto the stack, so the elements on the stack are 4,3,2,1. The next element is 1, and we’re going to push, and we’re going to push 4,3,2,1,1. The next element is 5, the top element is 1, the next element at the top of the stack is still 1, so we need the next element, which is 2, and we want to find the amount of water connected to the current layer.
We obtained the number of water connections in the second layer by using the four elements 2,1,1,5:1*3=3; 1 because min(2-1,5-1) is equal to min(1,4), and you can think about the barrel effect. The amount of water must be on the shortest board, so if the height is 1,3 because the index of 5 is 6 and the index of 2 is 2, there are 3 elements between them (3, 4, 5), which is 3 units. So it’s 6-2-1 is equal to 3.
When we take 1 off the stack, the top element becomes a 2, and the next element becomes a 3, so 3, 2, and 5 can also connect to water.
This is the water connection situation of the third layer, which can receive 4 units of water. Now we continue to push out stack 2, so our 4, 3 and 5 can still receive water.
This is our fourth layer of water, we can receive a total of 5 units of water, so we add up the total number of water, that is
1 + 3 + 4 + 5 = 13. Did you learn? Don’t worry, we still have giFs. Let’s get to the bottom of this.
Title code:
class Solution {
public int trap(int[] height) {
Stack<Integer> stack = new Stack<Integer>();
int water = 0;
// Special circumstances
if(height.length <3){
return 0;
}
for(int i = 0; i < height.length; i++){
while(! stack.isEmpty() && height[i] > height[stack.peek()]){
// Top of stack element
int popnum = stack.pop();
// the same element case is 1,1
while(! stack.isEmpty()&&height[popnum] == height[stack.peek()]){
stack.pop();
}
// Calculate the units of water in this layer
if(! stack.isEmpty()){
int temp = height[stack.peek()]; // The top element of the stack
/ / high
int hig = Math.min(temp-height[popnum],height[i]-height[popnum]);
/ / wide
int wid = i-stack.peek()-1;
water +=hig * wid;
}
}
// the index is pushed
stack.push(i);
}
return water;
}
}
Copy the codeIf you can feel that this article is very carefully written, can bring you a drop of help, can you please give this article a thumbs-up? So I have great motivation to write down, we need more classic topic OF THE DETAILED explanation of the GIF can pay attention to the public number: [Yuan Chu’s algorithm hut], more selected algorithm waiting for you, the original is not easy, thank you for watching