Leetcode11盛最多水的容器

11盛最多水的容器

给你 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。

示例：

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/container-with-most-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

遍历求解
时间复杂度：O(n2)
执行用时：1436 ms
内存消耗：6.2 MB

#define min(a, b) (((a) < (b)) ? (a) : (b))

int maxArea(int *height, int heightSize)
{
    int max = 0, area = 0;
    int i, j;
    for (i = 0; i < heightSize; i++)
    {
        for (j = i + 1; j < heightSize; j++)
        {
            area = (j - i) * min(height[i], height[j]);
            if (area > max)
                max = area;
        }
    }
    return max;
}

Solution 2

双指针
时间复杂度：O(n)
执行用时：12 ms
内存消耗：6.3 MB

int maxArea(int *height, int heightSize)
{
    int *l = height;
    int *r = height + heightSize - 1;
    int max = 0, area = 0;
    while (l < r)
    {
        if (*l < *r)
            area = (r - l) * *(l++);
        else
            area = (r - l) * *(r--);
        if (area > max)
            max = area;
    }
    return max;
}