更加丰富内容可查看我的个人博客：xukang’s blog
时间复杂度 O(N^2)
class Solution { public: int maxArea(vector<int>& height) { int res = 0; for (int i = 0; i < height.size() - 1; i++) { for (int j = i + 1; j < height.size(); j++) { res = max(res, min(height[i], height[j]) * (j - i)); } } return res; } };对于双指针方法，数组和链表相关题目经常会用到
时间复杂度 O(N)
为什么双指针的做法是正确的？
双指针代表了什么？
双指针代表的是 可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示 数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。在这之后，我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了。
为什么对应的数字较小的那个指针不可能再作为容器的边界了?
反正法 ： 假设当前左指针和右指针指向的数分别为 x 和 y，不失一般性，我们假设 x <= y。同时，两个指针之间的距离为 t 。那么，它们组成的容器的容量为： min(x, y) ∗ t = x ∗ t
我们可以断定，如果我们保持左指针的位置不变，右指针往左移，这个容器的容量就不会超过 x ∗ t了。
如果我们任意向左移动右指针，指向的数为 y1 ，两个指针之间的距离为 t1 ，那么显然有 t1 < t，并且 min (x, y1) <= min (x , y)：
如果 y1 <= y，那么 min(x, y1) <= min(x, y)；如果 y1 > y ， 那么 min(x, y1) = x = min(x, y);结合 t1 < t 和 min (x, y1) <= min (x , y) 得到 min(x, y1) ∗ t1 < min(x, y) ∗ t
即无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量。也就是说，我们可以通过移动指向较小值的那个指针，来遍历数组，达到减少时间复杂度的效果
class Solution { public: int maxArea(vector<int>& height) { int res = 0; int i = 0; int j = height.size() - 1; while (i < j) { // if (height[i] <= height[j]) { // res = max(res, height[i] * (j - i)); // i++; // } else { // res = max(res, height[j] * (j - i)); // j--; // } /* 三目表达式虽然优雅！但是容易犯错！ 如果(j - i) * height[i++] 写成 height[i++] * (j - i) 就出错了！ */ res = height[i] <= height[j] ? max(res, (j - i) * height[i++]) : max(res, (j - i) * height[j--]); } return res; } };