28. Rainwater connection

42. Rainwater collection

Given n Nonnegative integers indicate that each width is 1 Height map of columns of , Calculate columns arranged in this way , How much rain can be received after rain .

Example 1：

 Input ：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 Output ：6
 explain ： Above is an array of  [0,1,0,2,1,0,1,3,2,1,2,1]  Height map of representation , under these circumstances , Can connect  6  Units of rain （ The blue part indicates rain ）. 

Example 2：

 Input ：height = [4,2,0,3,2,5]
 Output ：9

public int trap(int[] height) {
    
    int sum = 0;
    // You don't have to think about the columns at the end of the line , Because there must be no water . So the subscript is from  1  To  length - 2
    for (int i = 1; i < height.length - 1; i++) {
    
        int max_left = 0;
        // Find the highest on the 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 end of 
        int min = Math.min(max_left, max_right);
        // Only the smaller segment is greater than the height of the current column will have water , There will be no water in other cases 
        if (min > height[i]) {
    
            sum = sum + (min - height[i]);
        }
    }
    return sum;
}

Monotonic stack

public int trap6(int[] height) {
    
    int sum = 0;
    Stack<Integer> stack = new Stack<>();
    int current = 0;
    while (current < height.length) {
    
        // If the stack is not empty and the current height is greater than the height of the top of the stack, the cycle will continue 
        while (!stack.empty() && height[current] > height[stack.peek()]) {
    
            int h = height[stack.peek()]; // Take out the element to be out of the stack 
            stack.pop(); // Out of the stack 
            if (stack.empty()) {
     //  Go out when the stack is empty 
                break; 
            }
            int distance = current - stack.peek() - 1; // The distance between the two walls .
            int min = Math.min(height[stack.peek()], height[current]);
            sum = sum + distance * (min - h);
        }
        stack.push(current); // Stack the currently pointed wall 
        current++; // Pointer backward 
    }
    return sum;
}