Given n n n n that n nonnegative integers represent the height of each column with a width of 1, calculate how much rain can be picked up after the rain falls on the columns arranged in this order.
Above is a height map represented by an array [0,1,0,2,1,0,1,3,2,1,2,1], in which case six units of rain can be received (the blue part represents rain)
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Solution 1: By column
For each column of water, we only need to focus on the current column and the highest wall on the left and the highest wall on the right.
Depending on the barrel effect, of course, how much water is filled, we only need to look at the tallest wall on the left and the shorter one on the tallest wall on the right.
Therefore, there are three cases according to the height of the shorter wall and the wall in the current column.
Shorter walls are taller than the walls in the current column
After determining the highest wall on the left and the highest wall on the right of the column you are asking for, we remove the unrelated wall for ease of understanding.
Now imagine filling water between the tallest walls on either side. How much water will the column being requested have?
Obviously, the shorter side, the height of the wall on the left, minus the height of the current column, which is 2 - 1 = 1, can hold a unit of water.
Shorter walls are less tall than the walls in the current column
Likewise, we remove the other unrelated columns.
Imagine filling water between the tallest walls on either side. How much water will the column being requested have?
The column being requested will not have water because it is larger than the shorter walls on both sides.
The height of the shorter wall is equal to the height of the wall in the current column.
As in the previous case, there is no water.
Understanding these three situations, the program is easy to write, traverse each column, and then find out the highest walls on either side of the column. Find the shorter end and compare it to the height of the current column. The result is the top three cases.
public int trap(int[] height) {
int sum = 0;
//The columns at the ends are not considered because there must be no water. So subscripts range from 1 to length - 2
for (int i = 1; i < height.length - 1; i++) {
int max_left = 0;
//Find the highest left
for (int j = i - 1; j >= 0; j--) {
if (height[j] > max_left) {
max_left = height[j];
}
}
int max_right = 0;
//Find the highest on the right
for (int j = i + 1; j < height.length; j++) {
if (height[j] > max_right) {
max_right = height[j];
}
}
//Find the smaller at both ends
int min = Math.min(max_left, max_right);
//Only a smaller section that is larger than the height of the current column will have water, otherwise there will be no water
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}Time complexity: O(n) ²)， Traversing through each column requires n to find out that the highest wall on the left and the highest wall on the right add up to exactly another n, so it's n ².
Spatial complexity: O(1).
Solution 2: Dynamic planning We note that Solution 1. For each column, we want the highest wall on the left and the highest wall on the right to go through all the heights again. Here we can optimize it.
Start with two arrays, max_left [i] represents the height of the highest wall on the left side of column i, max_right[i] represents the height of the highest wall to the right of column I. (It is important to note that the highest wall on the left (right) side of column I does not include itself, which is somewhat different from what is said above leetcode)
For max_ We can actually do this with left.
max_left [i] = Max(max_left [i-1],height[i-1]). Choose a larger height for the left side of the wall in front of it and the one in front of it, that is, the highest wall on the left side of the current column.
For max_ RightWe can ask for it.
max_right[i] = Max(max_right[i+1],height[i+1]). Choose a larger height for the right side of the wall behind it and for the wall behind it, which is the highest wall on the right side of the current column.
In this way, using the algorithm of Solution 1, we do not need to iterate over the max_once every time in the for loop. Left and max_right now.
public int trap(int[] height) {
int sum = 0;
int[] max_left = new int[height.length];
int[] max_right = new int[height.length];
for (int i = 1; i < height.length; i++) {
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
}
for (int i = height.length - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}Time complexity is not N*N because there is no loop inside loop The time complexity here is 3N, linear, so O(n)
Time complexity: O(n).
Spatial Complexity: O(n), which stores the highest wall on the left and the highest wall on the right for each column.