This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

Force button 42 catch rain as follows:

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

A, thinking

In fact, I just started to think: if you need to catch rain there must be a peak and valley, that is, first decrease and then increase. So finding all the peaks and valleys and peaks will give you an accurate calculation of the area.

The implementation code looks like this (error demonstration) :

public int trap(int[] height) {
    if (height == null || height.length<3)
        return 0;
    int ret = 0;
    int len = height.length;
    // Only when there are valleys can the rain be contained
    boolean down = false;
    int left = 0;
    List<Integer> boundary = new ArrayList<>();
    // Find all the valleys from left to right
    for (int i=1; i<len; i++) {
        if (height[i] >= height[i-1]) {
            left = i ;
            down = false;
        } else {
            if(! down) {// The trend is downward
                down = true;
                boundary.add(left);
                // If there are two elements
                if (boundary.size() == 2) {
                    // Calculate the height
                    ret += calc(height, boundary.get(0), boundary.get(1));
                    boundary.clear();
                    down = false; }}}}return ret;
}

public int calc(int[] height, int a, int b) {
    int ret = 0;
    int min = Math.min(height[a], height[b]);
    for (int i=a; i<=b; i++) {
        ret += Math.max(min - height[i], 0);
    }
    return ret;
}
Copy the code

But I find it impossible to deal with situations where the peak to the left of a particular peak or valley is not immediately adjacent to the current peak or valley

So the key to solving this problem is to find the highest point to the left and the highest point to the right of each subscript I

The overall step is divided into two steps:

1. Find all the subscriptsiThe correspondingLeft a peak 和 The highest point right
2. The traversal computes the area and: subscriptiThe corresponding area is zeroLower high minus current height (similar to barrel effect, depending on short board), the formula forMath.min(leftMax[i], rightMax[i]) - height[i]

The process of finding the highest point can be seen in the following example

For example (find the highest point)

Parameter Description leftMax[] : indicates the left highest point array

Here to find the left highest point as an example, the right highest point step is the same, so omit

= math.max (leftMax[i-1], height[I])

So all we need to do is walk through the array from left to right, and we can initialize the left highest point array

Tips: The above process is simple dynamic programming (using the state transition equation, solved from the bottom up)

Second, the implementation

The implementation code

The implementation code is consistent with the idea

public int trap(int[] height) {
    if (height == null || height.length<3)
        return 0;
    int ret = 0;
    int len = height.length;
    int[] leftMax = new int[len];   // I subscript and its highest left element
    int[] rightMax = new int[len];  // The highest element to the right of the I index
    // Initialize leftMax
    leftMax[0] = height[0];
    for (int i=1; i<len; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }
    // Initialize rightMax
    rightMax[len -1] = height[len - 1];
    for (int i=len-2; i>-1; i--) {
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }
    // Calculate the area
    for (int i=0; i<len; i++) {
        ret += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return ret;
}
Copy the code

The test code

public static void main(String[] args) {
    int[] nums = {4.2.0.3.2.5};
    new Number42().trap(nums);
}
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥