Monotonic stack -42 Connect rainwater

1. subject

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

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/trapping-rain-water

2. Their thinking

There are three ways to solve it ：

Method 1 ： Double finger needling

then , The height of rainwater in the current column is equal to ,min(LH,RH)- Current column height .

A special case ： The first and last columns do not operate .

Method 2 ： Dynamic programming

In fact, it is an optimization of the double pointer method , Because when using the double pointer method , Find out , When calculating the left and right maximum values of each column , There are repeated calculations , If dynamic programming method is used to record .

That is to traverse from left to right ：maxLeft[i] = max(height[i], maxLeft[i - 1]);

Traverse from right to left ：maxRight[i] = max(height[i], maxRight[i + 1]);

Method 3 ： Monotonic stack

There are three situations ：

（1） If the element currently traversed （ column ） The height is less than the height of the top element , Just add this element to the stack , Because the stack is supposed to keep the order from small to large （ From the top to the bottom of the stack ）.

（2） If the element currently traversed （ column ） The height is equal to the height of the top element of the stack , To update the top of the stack elements , Because when you meet a column of the same height , You need to use the right most column to calculate the width .

（3） If the element currently traversed （ column ） The height is greater than the height of the top element , And then there's the groove （ In this case, there will be rain ）

Its essence is ： The top of the stack and the next element at the top of the stack, as well as the three elements to be put into the stack, will receive water ！

Height of groove ：int h = min(height[st.top()], height[i]) - height[mid];

Width of groove ：int w = i - st.top() - 1 ;

Volume of groove ：h*w

3. Code

Method 1 ： Double finger needling （ Non optimal ）

public int trap(int[] height) {
    
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
    
            //  The first pillar and the last pillar don't receive rain 
            if (i==0 || i== height.length - 1) continue;
            
            int rHeight = height[i]; //  Record the highest height of the column on the right 
            int lHeight = height[i]; //  Record the maximum height of the left column 
            for (int r = i+1; r < height.length; r++) {
    
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i-1; l >= 0; l--) {
    
                if(height[l] > lHeight) lHeight = height[l];
            }
            int h = Math.min(lHeight, rHeight) - height[i];
            if (h > 0) sum += h;
        }
        return sum;

    }

Method 2 ： Dynamic programming

public int trap(int[] height) {
    
        int length = height.length;
        if (length <= 2) return 0;
        int[] maxLeft = new int[length];
        int[] maxRight = new int[length];
        
        //  Record the maximum height of the left column of each column 
        maxLeft[0] = height[0];
        for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
        
        //  Record the maximum height of the right column of each column 
        maxRight[length - 1] = height[length - 1];
        for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);
        
        //  Sum up 
        int sum = 0;
        for (int i = 0; i < length; i++) {
    
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }

Method 3 ： Monotonous stack method

public int trap(int[] height){
    
        int size = height.length;

        if (size <= 2) return 0;
        
        // in the stack, we push the index of array
        // using height[] to access the real height
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);

        int sum = 0;
        for (int index = 1; index < size; index++){
    
            int stackTop = stack.peek();
            if (height[index] < height[stackTop]){
    
                stack.push(index);
            }else if (height[index] == height[stackTop]){
    
                //  Because equal adjacent walls , The one on the left is impossible to store rainwater , therefore pop Sinister index, push Current index
                stack.pop();
                stack.push(index);
            }else{
    
                //pop up all lower value
                int heightAtIdx = height[index];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
    
                    int mid = stack.pop();
                    
                    if (!stack.isEmpty()){
    
                        int left = stack.peek();

                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(index);
            }
        }
        
        return sum;
    }

4. performance

Method 1 ： Double pointer （ Non optimal ）

• Time complexity ：O(n^2)
• Spatial complexity ：O(l)

Method 2 ： Dynamic programming

• Time complexity ：O(n)
• Spatial complexity ：O(n)

Method 3 ： Monotonic stack

• Time complexity ：O(n)
• Spatial complexity ：O(n)