Leetcode42. connect rainwater

【 difficult 】 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

Tips ：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

public int trap(int[] height) {
    
        int s = 0;
        //  Monotonically decreasing stacks   Only when the height is satisfied can water be saved , So let's save the index from big to small , Once the current value is greater than the value of the top element , It indicates that the water volume can be settled 
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
    
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
    
                int right = i;
                int mid = stack.pop();
                if (!stack.isEmpty()) {
    
                    int left = stack.peek();
                    s += (Math.min(height[left], height[right]) - height[mid]) * (right - left - 1);
                }
            }
            stack.push(i);
        }
        return s;
    }