A monotonic decreasing stack works well: when you encounter a bar taller than the stack top, water can pool between the two boundaries.

Trapping Rain Water

hard

Acceptance: 43%

StackMonotonic StackArray

You are given an array of non-negative integers that represent the height of bars in a cross-section. Each bar is one unit wide. Calculate the total volume of water that would be retained between the bars after rainfall. Solve this using a stack-based technique.

Examples

Example 1:

Input:height = [3,0,2,0,4]

Output:7

Example 2:

Input:height = [1,0,2,1,0,1,3]

Output:5

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Trapping Rain Water

Examples

Hints

Related Problems