力扣11题盛最多水的容器 c语言解题思路_c语言最大容器

题目

        11.给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

        说明：你不能倾斜容器。

        其实就是判断两边相距距离和两边最小值的乘积，结果只需要用一个max比较就行了，不需要输出两边和底部长度就很简单。

1.第一种解法：双指针

        如果是c语言学完，在判断这题的第一反应大部分应该都会是双指针，指针虽然比较难理解，但是不管在程序还是学习中，一般难理解的都是为了简便程序运行而做出的高级运用。

        当然，我的这段代码很长，看不懂不要紧，因为有更简便的方法。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
//主函数
int main(int argc, char const *argv[])
{
    //水的两边长度数据
    int nums[] = {1,8,6,2,5,4,8,3,7};
    //需要几个数组
    int size = sizeof(nums)/sizeof(nums[0]);
//
    //用来计算每个数组的元素个数
    int col = 0;
//
    //用来记录当前的面积数据
    int childnums[size * sizeof(int)];
    memset(childnums,0,size * sizeof(int));
//
    //建立数组记录元素个数col
    int colsize[size*sizeof(int)];
    memset(colsize,0,size * sizeof(int));
//
    //建立一个堆空间用来记录每个数组的首地址，用二级指针allstr访问堆空间
    int **allstr = (int **)calloc(size,sizeof(int *));
    if(allstr == NULL)
    {
        perror("calloc failed:");
        return -1;
    }
//
    //计算
    for(int i = 0; i < size -1;i++)
    {
        col = 0;
        for(int j = i+1; j < size; j++)
        {
            //对比两边的长度，计算盛水量，(盛水量是短边乘底)，并且记录到数组当中
            childnums[col++] = (nums[i] > nums[j] ? nums[j]*(j-i) : nums[i]*(j-i));
        }
//
        //申请堆空间存放数组，并且由指针temp访问堆空间
        int* temp = (int *)calloc(col,sizeof(int));
        memcpy(temp,childnums,col*sizeof(int));
//
        //将temp的首元素地址赋给allstr[i]
        allstr[i] = temp;
//
        //记录每个子集的元素个数
        colsize[i] = col;//数组的元素是 8 7 6 5 4 3 2 1 
    }
//
    //判断前面二级指针是否使用错误
    // for(int i = 0; i <size; i++)
    // {
    //     for(int j = 0;j < colsize[i];j++)
    //     {
    //         printf("%d ",allstr[i][j]);
    //     }
    //     printf("\n");
    // }
//
//     //建立一个数组用来存储
    int nums1[size*sizeof(int)];
    memset(nums1,0,size * sizeof(int));
 
    for(int i = 0; i < size; i++)
    {
        int k = 0;
        for(int j = 0;j < colsize[i] ; j++)
        {
            k = (allstr[i][j] > k ? allstr[i][j] : k);
        }
        nums1[i] = k;
    }
// //
//     //判断nums1是否可以正常输入
    // for(int i = 0; i < size; i++)
    // {
    //     printf("%d ",nums1[i]);
    // }
// //
    int max = 0;
    for(int i = 0; i < size; i++)
    {
        max = (max > nums1[i] ? max :nums1[i]);
    }
    printf("可以容纳的水量最大值是:%d\n", max);
//
    free(allstr);//释放堆空间
    allstr = NULL;
//
    return 0;
}

2.第二种解法：数组

        如果能看懂第一种解法的话（没看也不要紧），会发现指针在这里面的作用多余了，因为我们只需要计算最大值就可以了，指针的许多数据保存我们都用不到，这个时候就可以更简便一些，使用数组只将每个边与剩下的边乘积的最大值保存下来，不仅节省了空间还缩短了代码，增加了代码的可读性。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
 
// //主函数
int main(int argc, char const *argv[])
{
    //水的两边长度数据
    int nums[] = {1,8,6,2,5,4,8,3,7};
    //需要几个数组
    int size = sizeof(nums)/sizeof(nums[0]);
//
    //用来计算当前数组的元素个数
    int col = 0;
//
    //用来记录当前的面积数据
    int childnums[size * sizeof(int)];
    memset(childnums,0,size * sizeof(int));
//
    //建立一个数组用来存储
    int nums1[size*sizeof(int)];
    memset(nums1,0,size * sizeof(int));
//
    //计算
    for(int i = 0; i < size -1;i++)
    {
        col = 0;
        for(int j = i+1; j < size; j++)
        {
            //对比两边的长度，计算盛水量，(盛水量是短边乘底)，并且记录到数组当中
            col = (nums[i] > nums[j] ? nums[j]*(j-i) : nums[i]*(j-i));
        }
//
        for(int i = 0; i < size; i++)
        {
            int k = 0;
            for(int j = 0;j < col ; j++)
            {   
                k = (childnums[i] > k ? childnums[i] : k);
            }
            nums1[i] = k;
        }
    }
//
    int max = 0;
    for(int i = 0; i < size; i++)
    {
        max = (max > nums1[i] ? max :nums1[i]);
    }
    printf("可以容纳的水量最大值是:%d\n", max);
//
    return 0;
}

3.第三种解法：for循环

        有了简化的意识后，我就在思考，既然指针可以简化成数组，那数组能不能更加简化呢？当然能，因为我们只需要输出最大值，理论上一个只需要保存一个数字就可以了，这个时候我们就可以把数组也去掉，只留下一个max用来保存和输出最大值就可以了。

        我们可以直接将max放到计算容积的计算中去，判断max和容积哪个大，将大的值赋给max，然后进行下一个容积的判断，最终留下来的max就是最大的容积了。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
// //主函数
int main(int argc, char const *argv[])
{
    //水的两边长度数据
    int nums[] = {1,8,6,2,5,4,8,3,7};
 
    int size = sizeof(nums)/sizeof(nums[0]);
    int col = 0;
    int max = 0;
    //计算
    for(int i = 0; i < size -1;i++)
    {
        col = 0;
        for(int j = i+1; j < size; j++)
        {
            col = (nums[i] > nums[j] ? nums[j]*(j-i) : nums[i]*(j-i));
            max = max > col ? max : col;
        }
    }
    printf("可以容纳的水量最大值是:%d\n", max);
//
    return 0;
}

4.解法四：for循环-2

        如果把我的第三种方法直接用到力扣中去，会发现可以运行，但是提交会显示：运行时间超时，这个时候我们就要提到时间复杂度了。

        假设我的数组长度是s，我的第一个数字需要和后面的数字一共计算（s-1）的次数，第二个数字需要计算（s-2）的次数，以此类推，就相当于1=2+...+s的次数，相当于（s(s+1))/2的次数，非常麻烦。

        这个时候我们可以从两边同时开始计算，判断两边长度，在完成一次乘积后判断两边哪个长度短(数字更小)，就将其延伸下一位。

        例如num={1,2,3,4,5,9,8,7,6}，先计算乘积，然后判断1和6的大小，1的下标加一到2位，然后用2和6判断容积，，最后计算max，这样会节省很多不必要的计算，比如1和2的乘积等。只需压迫计算s-1次就可以了，大大简便了时间复杂度。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
 
// //主函数
int main(int argc, char const *argv[])
{
    //水的两边长度数据
    int nums[] = {1,8,6,2,5,4,8,3,7};
 
    int size = sizeof(nums)/sizeof(nums[0]);
    int L = 0;//左边数组下标
    int R = size -1;//右边数组下标
 
    int max = 0;
    while(L < R)
    {
        int  hight =  nums[L] > nums[R] ? nums[R] : nums[L];//判断两边哪个数字小，将小值赋给hight
        int  wide =   (R - L);//判断两下标相距长度
        int  are = wide * hight;//计算乘积
        if(max < are)//如果max小就将are给max，否则max就不改变
        {
            max = are;
        }
 
        if(nums[L] < nums[R])
        {
            L++;
        }
        else
        {
            R--;
        }
    }
    printf("可以容纳水的最大容积为:%d\n", max);
 
    return 0;
}

力扣解法标准形式

        如果是第一次使用力扣解题会发现自己写的代码在力扣上无法运行，因为力扣相当于为你准备好了输入输入和标准的数据，只需要写出计算的函数就可以了。

int maxArea(int* height, int heightSize){
}

        这段就是力扣给我们准备的子函数函数名（可以不用管）以及我们需要使用的数组名height，数组内容力扣已经自己准备好了，还有数组长度heightSize。

        我们只需要将自己的函数写出来，然后返回max的值就可以了。

    int indexLeft = 0;
    int indexRigt = heightSize -1;
 
    int maxAre = 0;
    while(indexLeft < indexRigt)
    {
        int  hight =  height[indexLeft] > height[indexRigt] ? height[indexRigt] : height[indexLeft];
        int  wide =   (indexRigt - indexLeft) ;
        int  are = wide * hight;
        if(maxAre < are)
        {
            maxAre = are;
        }
 
        if(height[indexLeft] < height[indexRigt])
        {
            indexLeft++;
        }
        else
        {
            indexRigt--;
        }
    }
    return maxAre;