题解 | #接雨水问题#

import java.util.*;

// class Pillar {
//     public Integer height;
//     public Integer index;

//     public Pillar(int height, int index) {
//         this.height = height;
//         this.index = index;
//     }
// }

// class Cmp implements Comparator<Pillar> {
//     @Override
//     public int compare(Pillar o1, Pillar o2) {
//         return o2.height.compareTo(o1.height);
//     }
// }

public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
//     public long maxWater (int[] arr) {
//         if (arr.length < 3) {
//             return 0;
//         }
//         List<Pillar> pillars = new ArrayList<>();
//         for (int i = 0; i < arr.length; i++) {
//             pillars.add(new Pillar(arr[i], i));
//         }
//         Collections.sort(pillars, new Cmp());

//         // 往右边
//         Pillar p1 = pillars.get(0);
//         long sum = 0;
//         for (int i = 1; i < pillars.size(); i++) {
//             Pillar p2 = pillars.get(i);
//             if (p1.index > p2.index) continue;
//             if (p1.index+1 == p2.index) continue;
//             for (int j = p1.index+1; j < p2.index; j++) {
//                 if (p2.height > arr[j]) {
//                     sum += p2.height - arr[j];
//                 }
//             }
// //            System.out.println("sum["+p1.index+"," + p2.index+"]:" + sum);
//             p1 = p2;
//         }
//         // 往左边
//         p1 = pillars.get(0);
//         for (int i = 1; i < pillars.size(); i++) {
//             Pillar p2 = pillars.get(i);
//             if (p1.index < p2.index) continue;
//             if (p1.index == p2.index+1) continue;
//             for (int j = p2.index; j < p1.index; j++) {
//                 if (p2.height > arr[j]) {
//                     sum += p2.height - arr[j];
//                 }
//             }
//             p1 = p2;
//         }

//         return sum;
//     }
    public long maxWater(int[] arr) {
        if (arr.length < 3) {
            return 0;
        }

        int maxIndex = 0;
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
                maxIndex = i;
            }
        }
        // 向左
        int right = 0;
        int left = arr[0];
        long water = 0;
        for (int i = 1; i < maxIndex; i++) {
            right = arr[i];
            if (left < right) {
                left = right;
            } else {
                water += left - right;
            }
        }
        right = arr[arr.length-1];
        for (int i = arr.length - 2; i > maxIndex; i--) {
            left = arr[i];
            if (right < left) {
                right = left;
            } else {
                water += right - left;
            }
        }
        return water;
    }
}