Count the accumulated rainfall in a 2D mountain range
It's possible to do it in \$O(n)\$ using \$O(n)\$ additional memory. For that we should find the amount of rain collected at each index in \$O(1)\$. It can be calculated from the heights of the highest mountain to the right and to the left: 

$$\tt{rainfall[i]} = \max(0, \min(\tt{leftHighest}, \tt{rightHighest}) - \tt{height[i]})$$

We can have the height to the left updated on the fly in the same loop, but we have to precalculate the heights to the right in a separate loop.

Here is the sample code:

import java.util.Arrays;

public class Solution {
    public static int getCollectedRainfall(int[] heights) {
        int[] highestToTheRight = Arrays.copyOf(heights, heights.length + 1);
        for (int i = heights.length - 1; i &gt;= 0; --i) {
            highestToTheRight[i] = Math.max(highestToTheRight[i], highestToTheRight[i + 1]);
        }

        int collectedRainfall = 0;
        int highestToTheLeft = 0;
        for (int i = 0; i &lt; heights.length; ++i) {
            collectedRainfall += 
                Math.max(0, Math.min(highestToTheLeft, highestToTheRight[i]) - heights[i]);
            highestToTheLeft = Math.max(highestToTheLeft, heights[i]);
        }

        return collectedRainfall;
    }
}