AlgoPressAppearance
题目描述
https://leetcode.cn/problems/container-with-most-water
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。
说明：你不能倾斜容器。 
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
提示：
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
思路：暴力法
根据题目意思，暴力法计算最大面积，会超时
参考代码
csharp
public class Solution {
public int MaxArea(int[] height) {
//两层循环，找到 minHight * 距离，暂存最大值
int max = 0;
for(int i=0; i<height.Length - 1; i++){
for(int j=i+1; j<height.Length; j++){
int area = Math.Min(height[i],height[j]) * (j-i);
max = Math.Max(area,max);
}
}
return max;
}
}
思路2 : 双指针
寻找左边或者右边比自己高的最远的那根柱子，从而可以计算面积。 双指针：第一次做很难想到这个解法
双指针的有效性证明，如果要包含到两边的柱子，首先把范围放到最大，我们固定住小的一边，那么另一边无论移动到那里，他的值都不会大于当前的面积乘积。 第二步，我们开始收缩，明显是收缩小的柱子，后面取得面积的可能性大。 所以我们收缩掉小的一边。 此时我们就把问题收缩了一步，数据集变小，剩下的用同样的方法处理。
参考代码
csharp
public class Solution{
public int MaxArea(int[] height){
int left = 0;
int right = height.Length - 1;
int max = 0;
while(left < right){
int area = Math.Min(height[left],height[right]) * (right - left);
max = Math.Max(max,area);
if(height[left] < height[right]){
left++;
}
else{
right--;
}
}
return max;
}
}