一道关于数组的算法题目，请用java实现。

Question

在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表，数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]。
假如开始下雨了，那么墙之间的水坑能够装多少水呢？

请用java实现（任意数组求出结果）

Answer 1

虽然方法很笨，还不知道还有另外的bug，欢迎指出，共同进步

 package lizo;

/**
 * Created by Lizo on 2014/9/2.
 */


public class test {
    public static void main(String[] args) {
        int a[] = {2, 5, 1, 2, 3, 4, 7, 7, 6,3,4};
        int len=a.length;//数组长度
        int begin = 0; //从哪个地方才开始查找凹形
        int capacity=0; //容积

        while (begin<len){
            //找出凹形的左边墙
            int left=findLeft(begin,a,len);
            //如果返回值等于数组的长度，则退出循环
            if(left==len){
                break;
            }
            //找出凹形的右边墙
            int right=findRight(left,a,len);
            //如果返回值等于数组的长度，则退出循环
            if(right==len){
                break;
            }
            //计算两个之间的容量
            capacity+=findCapacity(left,right,a);
            //重新设置查找下一个凹形开始的位置
            begin=right;
        }
        System.out.println(capacity);


    }



    private static int findLeft(int begin, int[] a, int len) {
        //查找左边墙的标准为，当前的墙的高度大于下一个墙的高度
        for(int i=begin;i<len-1;i++){
            if(a[i]>a[i+1]){
                return i;
            }
        }
        return len;
    }

    private static int findRight(int left, int[] a, int len) {
        boolean findBottom=false; //判断是不是找到了凹形的点
        int tempRight=0;
        //查找右边墙的标准为，当前墙的高度大于等于左边墙的高度
        for(int i=left+2;i<len;i++){

            if(!findBottom && a[i]>a[i-1]){
                findBottom=true;
                tempRight=i;
            }
            if(!findBottom) continue;
            //找到了凹形的点之后才开始找右边的墙
            else{
                if(a[i]>=a[left]){
                    return i;
                }
                if(a[i]>a[tempRight]){
                    tempRight=i;
                }
            }


        }

        return tempRight>0?tempRight:len;
    }

    private static int findCapacity(int left, int right, int[] a) {
        //找出左右墙的较低的强
        int min=Math.min(a[left],a[right]);
        int c=0;
        //计算凹形容积
        for(int i=left+1;i<right;i++){
            int tempc=min-a[i];
            c+=(tempc>0)?tempc:0;
        }
        return c;
    }

}