暴力求解法

开始时想到了暴力求解法，最差情况下是O(nn)的时间复杂度，很不幸，超时了。
但至少在面试的时候，可以在有限的时间内给出一个基本解法，思路是这样的：
1 在数组arr(left, right)中找出最大和第二大的数的位置pos1和pos2；这样就将arr划分成了3段：
left,..., pos1, ..., pos2, ..., right
2 arr(pos1~pos2)直接的容量s可以直接计算出来；
3 那么s(arr, left, right) = s + s(arr, left, pos1) + s(arr, pos2, right)
最优情况下，每次能对半划分，这个时间复杂度就是nlog(n)。
这个程序很容易写出来。

双指针法

这个确实很难想，基本思路就是将arr(left, right)内的总容积，通过每次移除一个边界元素的方式逐步计算出来，也就是：
s(arr, left, right) = x1 + s(arr, left+1, right)，1) 或者：
s(arr, left, right) = x2 + s(arr, left, right-1)，2)
假设arr[left] < arr[right]，那么具体用1)还是2)呢，也就是应该移除left，还是right呢？
1 如果移除小的那个，我们可以保证：max(arr[left], arr[right]) >= set(已移除左元素）
当再移除arr[left]时，显然可以立刻得到left上能容纳的最大容量，如下：
min(max(set(已移除左元素)), arr[right]) - arr[left] = max(set(已移除左元素) - arr[left]
而这个已移除左元素的max值，我们只需要使用一个lmax记录就可以了。
2 如果移除大的那个，我们在移除的时间点无法确定它能容纳的最大容量，因为我们无法确定剩余元素的最小值。
这样通过逐步移除较小的那个边界元素，我们就可以计算出最终的容量。
附上代码。

    long long maxWater(vector<int>& arr) {
        if(arr.size() < 3) return 0;
        int l = 0, r = arr.size()-1;
        long long sum = 0;
        int wl = arr[0], wr = arr[arr.size()-1];
        while(l <= r) {
            if(l == r) { // the last item
                int wmin = min(wl, wr);
                if(arr[l] < wmin) sum += wmin - arr[l];
                break;
            }
            if(arr[l] < arr[r]) {
                if(arr[l] < wl) sum += wl - arr[l];
                else wl = arr[l]; // update left max
                l++;
            } else {
                if(arr[r] < wr) sum += wr - arr[r];
                else wr = arr[r]; // update right max
                r--;
            }
        }
        return sum;
    }