接雨水算法 java实现

接雨水java实现

思路：通过两次循环 ，从前往后 和从后往前，找到能盛水的容器，然后减去中间的黑色部分即可

public static int getVolume(int[] a){

    int maxVolume = 0;
    int index = 0;
    //从前往后
    for (int i = 0; i < a.length; i++){
        if(a[index] <= a[i] && index < i){
            int mid = 0;
            for (int j = index +1; j < i; j++){
                mid += a[j];
            }
            maxVolume += a[index] * (i - index - 1) - mid;
            index = i ;
        }
    }
    int end = index;
    index = a.length -1;
    //从后往前
    for (int j = a.length -1; j >=end; j--){

        if(a[index] <= a[j] && index > j){
            int mid = 0;
            for (int i = index -1; i > j; i--){
                mid += a[i];
            }
            maxVolume += a[index] * ( index - j - 1) - mid;
            index = j ;
        }
    }

    return maxVolume;

}