原题描述

Given n non-negative integers $a1, a2, …, an$, where each represents a point at coordinate $(i, ai)$. $n$ vertical lines are drawn such that the two endpoints of line $i$ is at $(i, ai)$ and $(i, 0)$. Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

算法

朴素算法是遍历区间左边的$i$和区间右边的$j$的所有可能，时间复杂度是O(N^2)，显然不合适。所以我们想办法来减少比较的次数。
主要算法步骤如下：
1. $L = 0, R = n - 1$
2. 如果$a[L] < a[R]$，则$L++$
3. 否则$R–$
4. 重复2和3，直到$L>R$
5. 把遍历过程中容积$C$的最大值返回

这个算法可以被用来处理短板效应，即最终的容积取决于比较矮的那个板；所以在算法中当$a[L] < a[R]$时，说明$L$是短板，此时你再怎么往左调节$R$，都不可能使得容积变大，所以没有必要将$L$和$R-1, R-2，…，L+1$比较，这样就能够大大减少比较的次数，因此应该把$L$右移，调节这个短板

C++代码

class Solution {
public:
    int maxArea(vector<int> &height) {
        int max = 0, area;
        int start = 0, end = height.size() - 1;
        while (start < end) {
            if (height[start] > height[end]) {
                area = height[end] * (end - start);
                end --;
            } else {
                area = height[start] * (end - start);
                start ++;
            }
            if (area > max) {
                max = area;
            }
        }
        return max;
    }
};

Bug Free Procedure 从记事本直接写代码

2016.12.06 Bingo!!!一次性AC

2016.12.13 编译错误
1. 三元运算符使用错误是？+：而不是：+？