LeetCode程序员面试金典：接雨水

　　题目：

　　给定n个非负整数表示每个宽度为1的柱的高度图，计算根据此排列的柱下雨后能接收多少雨水。

　　示例 1：输入：height = [0，1，0，2，1，0，1，3，2，1，2，1]输出：6解释： 1、0、2、1、0、1、3、2、1 在这种情况下，可以连接表示的高度图 6 单位雨水(蓝色部分表示雨水)。

　　示例 2： 输入：height = 输出:99

　　代码实现： class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) { return 0; } int[] leftMax = new int[n]; leftMax[0] = height[0]; for (int i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } int[] rightMax = new int[n]; rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } int ans = 0; for (int i = 0; i < n; ++i) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans; }}