LeetCode盛最多水的容器——C

刺骨的言语ヽ痛彻心扉 2021-11-05 10:00 227阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/container-with-most-water

## 题目描述 ##

给定 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。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]  
示例:

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

## 题解 ##

**（1）暴力遍历**  
这道题我一看到就想到暴力解法，把全部的面积都算出来，比较大小得到最大的面积就可以了。  
**（2）双指针求解**  
随后提交成功，发现自己的耗时很长很长，然后就查看优秀的解法，发现了这种解法。  
简单来说就是从两边缩进，由于面积取决于短的那一端假设为m，所以要想得到比当前更大的面积，**短的那一端n必须舍弃**，**计算由短的一段得到此时的面积**，然后舍弃短的一端，向中间进一步，这样向中间靠拢时面积才会有变化，不然舍弃长的一端面积只会一直变小。

## 代码 ##

**（1）暴力遍历**

//第一种解法 （全部遍历） 
    int min(int x,int y){
    	return x<y?x:y;
    }
    
    int max(int x,int y){
    	return x>y?x:y;
    }
    
    int maxArea(int* height, int heightSize){
    	int res=0;
    	for(int i=0;i<heightSize-1;i++){
    		for(int j=i+1;j<heightSize;j++){
    			int area=(j-i)*min(height[i],height[j]);
    			res=max(area,res);
    		}
    	}
    	return res;
    }

**（2）双指针求解**

//第二种解法 （双指针求解） 
    int maxArea(int* height, int heightSize){
    	int left = 0;
    	int right = heightSize-1;
    	int Area=0,maxArea=0;
    	while(left<right){
    	    if(height[left] > height[right]){
    	        Area = (right-left)*height[right];
    	        right--;
    	    }
    	    else{
    	        Area = (right-left)*height[left];
    	        left++;
    	    }
    	    maxArea=Area>maxArea?Area:maxArea;
    	}
    	return maxArea;
    }

## 调试 ##

#include<stdio.h>
    #include<string.h>
    #include<malloc.h>
    
    int main(){
    	int height[]={1,8,6,2,5,4,8,3,7};
    	int *heights=(int*)height;
    	int heightSize=sizeof(height)/sizeof(int);
    	int max=maxArea(heights,heightSize);
    	printf("%d\n",max);
    	return 0;
    }

## 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]  
**（1）暴力遍历**  
耗时很长，虽然能够通过。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]  
**（2）双指针求解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211104/e759cb134147411994839d908f22dc0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211104/591d3d93ca2c4dfea8150ead4a060f76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: /images/20211104/dacceea778f64d9c9ccbc8def81c0a4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 3]: /images/20211104/f0337b0883d84819afcee1af464f7c04.png