编写了两种实现，一种是遍历数组，采用双指针，时间复杂度为O(N^2);一种是采用单调栈的实现，时间复杂度为O(N):

package com.me.leetcode;

import java.util.Stack;

public class Rain {

	public static void main(String[] args) {
		int[] height = new int[] {0,1,0,2,1,0,1,3,2,1,2,1};
		System.out.println(trap(height));
		System.out.println(trapByStack(height));
	}
	
	public static int trap(int[] height) {
		// 我们可以考虑求出每个柱子上可以接的雨水有多少，然后求出总和。
		int sum = 0;
		// 经分析发现，每个柱子上可以接的雨水其实和柱子左右两个最高的柱子中最小的那个决定的
		// 遍历数组
		for (int i = 0; i < height.length; i++) {
			
			int leftMax = height[i];
			for (int j = i; j >=0; j--) {
				if (height[j] > leftMax) {
					leftMax = height[j];
				}
			}
			
			int rightMax = height[i];
			for (int k = i; k < height.length; k++) {
				if (height[k] > rightMax) {
					rightMax = height[k];
				}
			}
			
			sum += (Math.min(leftMax, rightMax) - height[i]);
		}
		
		return sum;
	}
	
	public static int trapByStack(int[] height) {
		int sum = 0;
		// 存放每个柱子左边和右边最大的高度
		int[][] indexs = new int[height.length][2];
		
		// 需要维护一个单调递减栈，按照单调递减的原则遍历数组并入栈，如果不满足单调递减的栈中元素，则需要出栈。
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < height.length;i++) {
			// 把初始高度设置为柱子的高度，如果没找到，柱子左右最高的高度就是柱子本身
			indexs[i][0] = height[i];
			indexs[i][1] = height[i];
			
			if (stack.isEmpty()) {
				stack.push(i);
			} else {
				// 为了维护单调栈，需要把不满足条件的元素坐标退栈
				while (!stack.isEmpty() && height[stack.lastElement()] < height[i]) {
					// 弹出的元素坐标位置的柱子的最左边的最大值肯定是栈底元素（如果没有就是自身）
					int index = stack.pop();
					if(!stack.isEmpty()) {
						indexs[index][0] = height[stack.firstElement()];
					}
				}
				
				stack.push(i);
			}
			
		}
		
		// 对于栈中剩下的元素，需要退栈
		while (!stack.isEmpty()) {
			// 同样，对于栈中元素来说，左边最大的肯定是栈底的元素
			indexs[stack.lastElement()][0] = height[stack.firstElement()];
			int index = stack.pop();
			
			// 而栈中的元素应该是栈中元素坐标左边的所有元素的右边最大的数。
			for (int i = 0; i < index; i++) {
				if (height[i] < height[index]) {
					indexs[i][1] = height[index];
				}
			}
		}
		
		for (int i = 0; i < height.length; i++) {
			sum += (Math.min(indexs[i][0], indexs[i][1]) - height[i]);
		}
		
		return sum;
	}

}

Q.E.D.