Monotonous stack -- 42. Receiving rain -- a difficult problem that big factories must know

1 Title Description

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 .

2 Title Example

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

3 Topic tips

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

4 Ideas

Maintain a monotone stack , The monotone stack stores subscripts , Satisfy the array corresponding to the subscript from the bottom of the stack to the top of the stack \textit{height}height Decreasing elements in .
Traversing the array from left to right , Traverse to subscript i when , If there are at least two elements in the stack , The top element of the stack is top,top The next element of is left, There must be height[lefft]≥ height[top]. If height[i]> height[top], Then we get ― An area that can receive rainwater , The width of this area is i- left - 1, Height is min( height[left , height[i]) — height[top], According to the width and height, the amount of rainwater that can be received in this area can be calculated .
In order to get left, Need to put top Out of the stack . In the face of top After calculating the amount of rain that can be received ,left Become new top, Repeat the above operation , Until the stack becomes empty , Or the subscript at the top of the stack corresponds to height The element in is greater than or equal to height[i].
On the subscript à After calculating the amount of rain that can be connected , Put the main stack , Continue to traverse the following subscripts , Calculate the amount of rain that can be received . After traversing, you can get the total amount of rainwater that can be received .
Complexity analysis
Time complexity :O(n), among n It's an array height The length of . from О To n —1 At most, each subscript of will only be put into and out of the stack ─ Time .
Spatial complexity :O(n), among n It's an array height The length of . The space complexity mainly depends on the stack space , The stack size will not exceed n.

5 My answer

class Solution {
    
    public int trap(int[] height) {
    
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
    
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
    
                int top = stack.pop();
                if (stack.isEmpty()) {
    
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}