数据结构

1. 原生java数组

思路

举例测试数据

[3,1,2,5,4,2]

具体理解思路

1. 从数组第一个位置开始向后步进式上探大于等于当前位置的第一个元素；
2. 如果一种取到目标元素E，这里为5，对应的index为3；则返回为对数组做过逆序动作，且给出起始index，这里分别是0,3；
3. 截取容器数组，这里为[3,1,2,5]
4. 计算容器容量，这个很简单，不做阐述，唯一注意的就是要选出容器数组收尾中较小的作为上限；
5. 截取剩余容器测试空间，即[5,4,2]；
6. 重复第一步，发现没有满足条件的，则做逆序动作重复第一步，第一次循环找出2和4，但二者相邻，更新出发index为1，继续上探，找到5，二者相邻，最后发现没有合适的容器，返回空数组表示未找到合适的容器
7. 补充一点：数组中如果不是全部一样大的话，一定存在一个位置的数比当前位置大，如果不存在，那么逆序后一定存在，所以代码实现里有一个一度递归的动作

以上动作实际是个循环，但为了理解，写成了过程化内容，有了这个过程看代码应该容易很多，下方为code

code

    private static final int[] EMPTY = new int[0];

    public long maxWater(int[] arr) {
        if (arr == null || arr.length <= 2) {
            return 0L;
        }

        long total = 0;

        while (arr.length > 2) {
            int[] result = findSubArrIndex(arr, 0);
            if (result.length == 0) {
                return total;
            }

            if (result[2] == 1) {
                arr = reversArr(arr);
            }
            int[] container = Arrays.copyOfRange(arr, result[0], result[1] + 1);
            arr = Arrays.copyOfRange(arr, result[1], arr.length);
            total += calc(container);
        }

        return total;
    }

    public static int[] findSubArrIndex(int[] arr, int depth) {
        if (arr.length <= 2) {
            return EMPTY;
        }

        int[] result = new int[3];

        int len = arr.length;
        int first = arr[0];
        result[0] = 0;
        for (int i = 1; i < len; i++) {
            int cur = arr[i];
            if (cur >= first && (i - result[0]) > 1) {
                result[1] = i;
                if (depth == 0) {
                    result[2] = 0;
                } else {
                    result[2] = 1;
                }
                return result;
            } else if (cur >= first) {
                result[0] = i;
                first = arr[i];
            }
        }

        depth++;
        if (depth > 1) {
            return EMPTY;
        }

        return findSubArrIndex(reversArr(arr), ++depth);
    }

    public static int[] reversArr(int[] arr) {
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            result[arr.length - i - 1] = arr[i];
        }
        return result;
    }

    public static long calc(int[] container) {
        if (container == null || container.length <= 2) {
            return 0L;
        }

        long total = 0L;
        int first = container[0] > container[container.length - 1] ? container[container.length - 1] : container[0];
        for (int i = 1; i < (container.length - 1); i++) {
            total += (first - container[i]);
        }
        return total;
    }

其他优化

1. 时间复杂度上优化空间不大；
2. 重点可优化空间复杂度，但是懒做了，有兴趣各位自己尝试；