计算容器盛水

这题其实不难，就是有点烦，做法为模拟实际情况，从左到右遍历数组，找出一个“桶”，然后计算盛水量。寻找桶的方式为寻找它的左右边界。

为了逻辑清晰，这里使用了状态机，整体分为三个状态：

1. 寻找左边界状态
2. 寻找右边界状态
3. 寻找最优右边界状态

于是上述三个状态下的行为分别是：

1. 向右寻找第一个降序点
2. 向右寻找第一个升序点
3. 向右寻找更高的右边界

在状态 3 时，成桶的条件有两个：

1. 找到了一个比左边界更高的右边界。（不可能更高了，更高就向左边溢出了）
2. 没找到最优的右边界，但数组结束了。此时我们取记录下来的右边界计算水，然后把遍历指针回退到这个右边界上。

    public long maxWater (int[] arr) {
        int leftBound = -1, rightBound = -1;
        long sum = 0;
        int state = 0;
        int index = 0;

        while (index < arr.length) {
            switch (state) {
                case 0: {
                    // 找到第一个降序邻居，作为左边界
                    if ((index < arr.length - 1) && (arr[index] > arr[index + 1])) {
                        leftBound = index;
                        state = 1;
                    }

                    ++ index;
                    break;
                }
                case 1: {
                    // 找到第一个升序邻居，作为右边界
                    if ((index < arr.length - 1) && (arr[index] < arr[index + 1])) {
                        rightBound = index + 1;
                        state = 2;
                    }

                    ++ index;
                    break;
                }
                case 2: {
                    // 比当前右边界更高的边界更优
                    if ((index < arr.length - 1) && (arr[index + 1] > arr[rightBound])) {
                        rightBound = index + 1;
                    }

                    /**
                        1. 右边界高于左边界时，此右边界为最优。
                        2. 没有触发最优右边界条件，但已经到了数组末尾。

                        取当前记录的最优右边界计算，然后回退到此右边界继续
                     */
                    if ((index == arr.length - 1) || (arr[rightBound] >= arr[leftBound])) {
                        sum += water(arr, leftBound, rightBound);
                        state = 0;
                        index = rightBound;
                        continue;
                    }

                    ++ index;
                    break;
                }
                default:
                    break;
            }
        }
        return sum;
    }

    public long water (int[] arr, int left, int right) {
        int min = Math.min(arr[left], arr[right]);
        long sum = 0;
        for (int i = left + 1; i < right; ++ i) {
            if (min > arr[i]) {
                sum += min - arr[i];
            }
        }
        return sum;
    }