盛最多水的容器

LeetCode第十一题

题目描述：
给你 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）
链接：https://leetcode-cn.com/problems/container-with-most-water

思路

第一种：直接简单暴力法，两层循环，时间复杂度为平方级别
第二种：首尾双指针法。当初始两个指针指向首尾时，底部为最大值。此时指针的移动有两种方式，一个是将左指针增大，一个是将右指针减少。不管是哪一种，底部都要减1，而高取的是左右中小的那个值。所以应该不能将高的那个指针移动，应该移动较小的那个值的指针。

源代码

//方法一：暴力法
int min(int num1,int num2){
    if(num1 < num2)
        return num1;
    else
        return num2;
}


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

//方法二：双指针法
int min(int num1,int num2){
    if(num1 < num2)
        return num1;
    else
        return num2;
}

int maxArea(int* height, int heightSize){
    int left = 0;
    int right = heightSize - 1;
    int v_max = 0;
    int volume;
    while(left < right){
        volume = (right - left) * min(height[left],height[right]);
        if(volume > v_max)
            v_max = volume;
        if(height[left] < height[right])
            ++left;
        else
            --right;
    }
    return v_max;
}

分析

采用双指针法时间复杂度为线性级别，空间复杂度为常数级别。