Rainwater problem

Topic describes

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] output:6Explanation: The above is made up of arrays [0.1.0.2.1.0.1.3.2.1.2.1] represents the height diagram, in this case, can be connected61 unit of rain (blue indicates rain).Copy the code

Example 2:

Enter: height = [4.2.0.3.2.5] output:9
Copy the code

Tip:

  • n = = h e i g h t . l e n g t h n == height.length n==height.length
  • 0<=n<=3 * 104 0<=n<=3∗104
  • 0 < = h e i g h t [ i ] < = 105 0 <= height[i] <= 105 0<=height[i]<=105

As shown in the figure, for a specific position he I ght[I] height[I] height[I], the given column width is 1. Therefore, the amount of rain water that may be received at this position is only dependent on the height. H e I ght[I] height[I] height[I] height[I] how much water can be connected to the position, also depends on the situation on both sides of it. M ax_left Max \_left max_left max_r I ght Max \_right max_right, And the maximum amount of water connected only depends on the minimum height m I n(max_left,max_r I ght) min(Max \_left, Max \_right) min(max_left,max_right).

  • If m I n(max _left, max _ r I g h t) > h e I g h t (Max \_left, Max \_right) >height[I] min(max_left,max_right)>height[I], he I ght[I] height[I
  • If min ⁡ (max _left, max _ r I g h t) < h e I g h t [I] \min(Max \_left, Max \_right)

How do you understand that? Take 🌰 as an example:

  • H e I ght height[1] height[1]


    The highest left is 0, the highest right is 3, and the current position is 1. According to the above principle, this position cannot receive water

  • [3] height[3] height[3]


    The highest on the left is 1, the highest on the right is 3, and the current position is 1, so the position can not connect to water

  • [7] height[7] height[7] Height [7]


    The highest left is 2, the highest right is 3, and the current position is 1. Meet the above principle of water access, therefore, Min ⁡ (m a x _ l e f t, m a x _ r I g h t) − H e I g h t [7] = min ⁡ (2, 3) – 1 = 1 / min (Max \ _left, Max \ _right) – height [7] = \ = 1 min min (2, 3) – 1 (max_left max_right) – height [7] = min (2, 3) = 1-1

So, H e I ght[I] height[I] height[I] height[I] height max_l ft Max \_left max_left max_ r I ght Max \ _right max_right.

M ax_left Max \_left max_left and max_r I ght Max \_right max_right. H e I ght[I] height[I] height[I] max_left Max \_left max_left

int max_left = 0;
for(int j = i - 1; j >= 0; j--){
    if(height[j] > max_left){ max_left = height[j]; }}Copy the code

M ax_r I ght Max \_right max_right = max_r I ght Max \_right

int max_right = 0;
for(int j = i + 1; j < height.length; j++){
    if(height[j] > max_right){ max_right = height[j]; }}Copy the code

M ax_left Max \_left max_left and max_r I ght Max \_right max_right The range of discussion is [1, L en(he I ght)−1) [1,len(height) -1) [1,len(height)−1) because rain water is not possible at both ends.

  • H I eght[1] hieght[1] : M ax_left=0 Max \_left=0 max_left=0, max_r I ght=3 Max \_right=3 max_right=3


  • H I eght[2] hieght[2] : M ax_left=1 Max \_left=1 max_left=1, max_r I ght=3 Max \_right=3 max_right=3


  • H I eght[3] hieght[3] : M ax_left=1 Max \_left=1 max_left=1, max_r I ght=3 Max \_right=3 max_right=3


  • H I eght[4] hieght[4] : M ax_left=1 Max \_left=1 max_left=1, max_r I ght=3 Max \_right=3 max_right=3


  • H I eght[5] hieght[5] : M ax_left=2 Max \_left=2 max_left=2, max_r I ght=3 Max \_right=3 max_right=3


  • H I eght[6] hieght[6] : Max_left =2, max_left=2, max_right=3, max_right=3, max_right=3, max_right=3


  • H eght[7] hieght[7] hieght[7] : M ax_left=2 Max \_left=2 max_left=2, max_r I ght=3 Max \_right=3 max_right=3


  • H I eght[10] hieght[10] : M ax_left=3 Max \_left=3 max_left=3, max_r I ght=2 Max \_right=2 max_right=2


  • H eght[11] hieght[11] Hieght [11] : M ax_left=3 Max \_left=3 max_left=3, max_r I ght=1 Max \_right=1 max_right=1


Through the above step by step analysis, the final water connection is 6. The detailed solution code is as follows:

/ * * *@Author dyliang
 * @Date2020/11/10 yea *@Version1.0 * /
public class _42 {
    public static void main(String[] args) {
        int[] height = {0.1.0.2.1.0.1.3.2.1.2.1};
        System.out.println(trap4(height));
    }

    public static int trap2(int[] height){
        int sum = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            for(int j = i - 1; j >= 0; j--){
                if(height[j] > max_left){ max_left = height[j]; }}int max_right = 0;
            for(int j = i + 1; j < height.length; j++){
                if(height[j] > max_right){ max_right = height[j]; }}int min_one = Math.min(max_left,max_right);
            sum += Math.max(0, min_one - height[i]);
        }
        returnsum; }}Copy the code

M ax_left Max \_left max_left and M ax_r I ght Max \_right max_right, The time complexity is O(N2) O(N^2) O(N2). The space complexity is O(1) O(1) O(1) because no additional storage space is used during the procedure.

M ax_left Max \_left max_left and max_r I ght Max \_right max_right have not changed in many positions, as shown in the yellow box below. M ax_left Max \_left max_left and max_r I ght Max \_right max_right are the same for all positions in each box. If we find and store the max_left Max \_left max_left and max_r I ght Max \_right max_right in advance, Then the time to find the water connection is reduced to O(N) O(N) O(N). Although the space complexity becomes O(N) O(N) O(N) O(N), space over time is perfectly acceptable.


M ax_left Max \_left max_left and max_r I ght Max \_right max_right M ax_left Max \_left max_left he ght[I] height[I] M ax_left[I] Max \_left[I] max_left[I] depends on he I ght[I −1] height[I -1] height[I −1] and he I ght[I] M ax_left[I −1] Max \_left[I −1] max_left[I −1] And max_left[I] Max \_left[I] max_left[I] is the maximum value of both.

M ax_r I ght Max \_right The max_right array depends on the right half of each position, so it needs to be traversed from right to left, The corresponding principle is max _ r I g h t [I] = Max ⁡ (max _ r I g h t [I + 1], h e i g h t [ i + 1 ] ) max\_right[i] = \max(max\_right[i + 1], Height) [I + 1] max_right [I] = Max (max_right [I + 1], the height [I + 1]).

The detailed solution code is as follows:

/ * * *@Author dyliang
 * @Date2020/11/10 yea *@Version1.0 * /
public class _42 {
    public static void main(String[] args) {
        int[] height = {0.1.0.2.1.0.1.3.2.1.2.1};
        System.out.println(trap4(height));
    }

    public static int trap3(int[] height){
        int sum = 0;
        int h = height.length;
        int[] max_left = new int[h];
        int[] max_right = new int[h];

        for (int i = 1; i < h - 1; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }

        for (int i = h - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }

        for (int i = 1; i < h - 1; i++) {
            int min_one = Math.min(max_left[i], max_right[i]);
            sum += Math.max(0, min_one - height[i]);
        }
        returnsum; }}Copy the code

The time complexity and space complexity of the memory-based method above are both O(N) O(N) O(N) O(N). Since the array is always iterated at least once, the minimum time complexity can only be O(N) O(N) O(N), so can we do it without extra storage space?

H e I ght height[I] height[I] height[I] max_left Max \_left max_left M ax_left Max \_left max_left M ax_r I ght Max \_right max_right max_r I ght Max \_right max_right M ax_r I ght Max \_right max_right Therefore, we can use two variables to record the current maximum max_left Max \_left max_left and M ax_r I ght Max \_right max_right. The traversal of positions at both ends can be recorded using Pointers L E F T left left and R I G H T right right.

And for left left left, its corresponding max_left Max \_left max_left does not change, while max_r I ght Max \_right max_right does not. Because, left left left to max_r I ght Max \_right max_right corresponding index position may exist larger values. Similarly, for r I ght right, max_r I ght Max \_right max_right does not change, but M ax_left Max \_left max_left may change. M ax_left<max_r I ght Max \_left < Max \_right max_left<max_right If a larger max r I ght Max \_right max_right occurs, it will not affect the current result according to the principle of water connection. M ax_r I ght>max_left Max \_right > Max \_left max_right>max_left Even if a larger max_left Max \_left max_left does not affect the current result.

The detailed solution code is as follows:

/ * * *@Author dyliang
 * @Date2020/11/10 yea *@Version1.0 * /
public class _42 {
    public static void main(String[] args) {
        int[] height = {0.1.0.2.1.0.1.3.2.1.2.1};
        System.out.println(trap4(height));
    }

     public static int trap(int[] height) {
        int sum = 0;
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        while(left <= right){
            // Handle the position indicated by left
            if(left_max < right_max){
                // Record the water connection
                sum += Math.max(0, left_max - height[left]);
                // Update possible max_left
                left_max = Math.max(left_max, height[left]);
                left++;
             // Handle the position indicated by right
            } else {
                // Record the water connection
                sum += Math.max(0, right_max - height[right]);
                // Update possible max_rightright_max = Math.max(right_max, height[right]); right--; }}returnsum; }}Copy the code