Requirements:

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:

Input:0.1.0.2.1.0.1.3.2.1.2.1] output:6
Copy the code

Ideas:

It’s essentially evaluating by column. Focus on the current column, the highest wall to the left and the highest wall to the right. And pay attention to the height of the shorter wall of the highest wall on the left and right.

  • The height of the lower wall is higher than that of the current column, and the water stored is (height of the lower wall – height of the current column)
  • The height of the lower wall is equal to the current column and the amount of water stored is 0
  • The height of the lower wall is less than the current column and the water storage is 0
  • In addition, both ends are certainly unable to hold water
public int trap(int[] height) {
    int sum = 0;
    // Don't worry about both ends
    for (int i = 1; i < height.length - 2; i++) {
        int max_left = 0;
        // Find the highest left wall and traverse from right to left from the current column
        for (int j = i-1; j >= 0; j--) {
            if(height[j] > max_left) { max_left = height[j]; }}int max_right = 0;
        // Find the highest wall on the right and walk from left to right from the current column
        for (int j = i+1; j < height.length; j++) {
            if(height[j] > max_right) { max_right = height[j]; }}// Compare the two highest walls to find the lower wall
        int min = Math.min(max_left, max_right);
        if(min > height[i]) { sum += (min - height[i]); }}return sum;
}
Copy the code

Dynamic programming for optimization

Max_left [I] represents the height of the highest wall on the left of column I and max_right[I] represents the height of the highest wall on the right of column I. In fact, max_left[i]=max(max_left[i-1], height[i-1]), max_right[i] = max(max_right[i+1], Height [I +1]) so you don’t have to evaluate max_left and max_right again each time in the loop. But there are still drawbacks, such as traversing from left to right, and the need for arrays to store the largest walls on the left and right sides.

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-1; 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 += (min-height[i]); }}return sum;
}
Copy the code

Double pointer improvements:

In this case, both max_left[I] and max_right[I] are used only once, so you can use double Pointers alternately to avoid arrays. Max_left = math. Max (max_left, height[i-1]); max_left = math. Max (max_left, height[i-1]) If height[left-1]

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;/ / pointer to the left
    int right = height.length - 2;/ / right pointer
    for (int i = 1; i < height.length - 1; i++) {
        // Update from left to right
        if (height[left-1] < height[right+1]) {
            max_left = Math.max(max_left, height[left-1]);
            int min = max_left;
            if (min > height[left]) {
                sum += (min-height[left]);
            }
            left++;
        } else {// Update from right to left
            max_right = Math.max(max_right, height[right+1]);
            int min = max_right;
            if(min > height[right]) { sum += (min - height[right]); } right--; }}return sum;
}
Copy the code