题目

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

来源：力扣（LeetCode）

题解

一开始我上手来是直接写了暴力扫描法（和冒泡排序类似）。看评论和官方题解的第一眼看到“双指针法”这几个字的时候我就明白了另一种解法。
毕竟暴力遍历的时间复杂度是O(n^2)，而使用双指针法则可以直接提高到O(n)，这是长足的飞跃。

暴力法

虽说我很蠢，一开始只是想到了暴力遍历，但是我在遍历过程中也增加了一步剪枝，就是在指针二second的开始位置的选定时候，我没有选择first+1，而是second = first + max/height[first] + 1，或许是借助了一点动规的思想，想要通过已有的最大面积来进行一些无用指针二的跳过来提高速度。

这段剪枝的思想可以理解为，以当前选中的指针一（first）作为两根指针中的短根，用已经记录到的最大面积来除这根指针一，以获得底宽，由指针一的位置直接加上这个底宽便可以直接跳过中间的这些无论是长还是短的无用的指针二了。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0, n = height.size();
        for (int first = 0; first < n; first++) {
            if (height[first] == 0) {
                continue;
            }
            for (int second = first + max/height[first] + 1; second < n; second++) {
                int s = min(height[first], height[second]) * (second - first);
                if (s > max) {
                    max = s;
                }
            }
        }
        return max;
    }
};

性能：340 ms 9.8 MB

双指针法

class Solution {
public:
    inline int Max(const int& a, const int& b) {
        return a>b?a:b;
    }
    inline int Min(const int& a, const int& b) {
        return a<b?a:b;
    }
    int maxArea(vector<int>& height) {
        register int result = 0;
        register int former = 0, later = height.size() - 1;
        while (former < later) {
            result = Max(result, Min(height[former], height[later]) * (later - former));
            height[former]<height[later]?former++:later--;
        }

        return result;
    }
};

性能：36 ms 9.7 MB

双指针法 + 奇技淫巧

static auto x = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}();

class Solution {
public:
    inline int Max(const int& a, const int& b) {
        return a>b?a:b;
    }
    inline int Min(const int& a, const int& b) {
        return a<b?a:b;
    }
    int maxArea(vector<int>& height) {
        register int result = 0;
        register int former = 0, later = height.size() - 1;
        while (former < later) {
            result = Max(result, Min(height[former], height[later]) * (later - former));
            height[former]<height[later]?former++:later--;
        }

        return result;
    }
};

心得

又学到了一种刷题的奇技淫巧，着实是“开心”啊。

static auto x = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}();

这段代码的重点在于：c++中cin默认与stdin同步以使得文件指针不混乱，同时cout和stdout也一样，这导致了cin有额外的开销，所以会更花时间。

std::ios::sync_with_stdio(false);这一句关闭了cin和stdin的同步，使得速度与scanf几乎相同。

reference：leetcode里这段强行加快运行速度的C++代码是什么意思？ - riba2534的回答 - 知乎

使用的时候可能造成文件指针混乱，因为代码可能会在stl初始化之前跑，然后GG，实际工程切勿使用。

结果

执行用时 : 12 ms, 在所有 C++ 提交中击败了99.74%的用户
内存消耗 : 9.7 MB, 在所有 C++ 提交中击败了86.13%的用户