本文共 1481 字，大约阅读时间需要 4 分钟。

存储雨水

问题描述：给定N个非负整数表示一个高度圈，每一个条的宽度为1个单位，计算雨后，该高度圈能够存储雨水的量（多少单位的雨水）。

例如：给定的数组为 [0,1,0,2,1,0,1,3,2,1,2,1]；返回值为：6

原题描述如下：Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

问题分析：根据题目描述的意思，设计一张图比较直观：

假设给出高度圈的正视图，每一个方格表示一个单位的雨水量，并且每一个条的宽度为1个单位。绿色表示梁，蓝色表示洼地，能够存储雨水。根据给定的高度数组，先把梁全部标出来。然后在寻找洼地存储雨水，最后求和。能够存储雨水的洼地用蓝色表示。从图可以看出，可以存储 6 个单位的雨水。

算法设计

package com.bean.algorithmbasic;public class RainWaterDemo {    /*     * 算法设计：存储雨水     * */    public static int trap(int[] A) {        if (A.length <= 2)            return 0;        int[] leftMaxHeight = new int[A.length];        leftMaxHeight[0] = 0;        int maxh = A[0], len = A.length;        for (int i = 1; i < A.length; i++) {            leftMaxHeight[i] = maxh;            if (maxh < A[i])                maxh = A[i];        }        int right = A[len - 1], left, sum = 0;        for (int i = len - 2; i > 0; i--) {            left = leftMaxHeight[i];            int minh = Math.min(right, left);            if (minh > A[i])                sum += minh - A[i];            if (right < A[i])                right = A[i];        }        return sum;    }    public static void main(String[] args) {        // TODO Auto-generated method stub        int[] arrayDemo = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };        System.out.println("ANSWER is " + trap(arrayDemo));    }}

运行结果为： 6

（完）