LeetCode 011 — Container With Most Water

https://leetcode.com/problems/container-with-most-water/

给定一个整型数组，表示坐标轴上的一组相应长度的垂直于 x 轴的线段，要求找出两条线跟 x 轴围起来的容器，能装最多的水。

这题一开始我想用最暴力的方法做两层循环O(n^2)的解法提交试一下，可惜超时了，果然 Medium 难度的题目不会这么轻松放我过去的。

既然 O(n^2) 的解法没有办法通过，那就要想办法能不能找出 O(n) 的解法，一遍循环弄出来。我绞尽脑汁想了很久，尝试了好几种方案，始终没有办法解决。我最终不得不求助于前人的经验，看到别人的解法之后，顿时觉得豁然开朗。

Solution

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0;
        int area = 0;
        int i = 0;
        int j = height.size() - 1;
        while(i < j) {
            if(height[i] > height[j]) {
                area = (j - i) * height[j];
                --j;
            }
            else {
                area = (j - i) * height[i];
                ++i;
            }
            if(area > max_area) {
                max_area = area;
            }
        }

        return max_area;
    }
};

其实这个解法的关键是用两个指针，分别从左右两边向中间开始遍历，每次算出当前两个指针所指的线围成的面积，并比较是不是当前最大的记到 max_area 里，然后每次排除较短的一条线段，继续遍历。

为什么这里每次可以排除较短的一条线段呢？因为我们是从两边开始向中间遍历的，也就意味着我们是从横坐标宽度 j-i 最大开始的，当一条短的线段在横坐标宽度比较大的时候才有机会获得最大的面积，当横坐标宽度 j-i 越来越小的时候，这条线段所围成的面积肯定比之前的一次循环小，所以可以直接排除掉。并且我们在排除之前已经把可能的最大面积记到了 max_area 里，所以直接排除掉短的线段，对结果不会有影响。