@力扣习题集
习题十一：盛最多水的容器
来源：力扣（LeetCode）
传送门：习题直达
本文参考力扣上大神的想法思路等，仅作为个人的习题笔记，如有冒犯我就设置仅个人可见。
题目描述
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
解题思路
1、暴力解法：双重 for 循环
emmm…这应该是像我这种菜鸡的脑袋里第一时间想到的解法了吧！！！啊！！！惭愧！！！
不多说直接上代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int Max=0,res=0;
int s,len,h;
int num=height.size();
for(int i=0; i<num-1; i++)
{
for(int j=i+1; j<num; j++)
{
len=j-i;
h=min(height[i],height[j]);
s=len*h;
res=max(res,s);
}
Max=max(Max,res);
}
return Max;
}
};
唰唰唰，一顿操作写完代码！酣畅淋漓！！！内心窃喜，第一次不费力气做了一道中等难度的题！调试没问题，激动提交了！
写的快，打脸也是很快的！真疼！！！
超出时间限制了呀。其实自己在写的时候就已经想到了这个问题，奈何自己头铁。。。
2、版本答案：双指针解法
看到双指针，可能很多人恍然大悟，就知道如何解了！
[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
这里主要记录一下，指针移动的条件：
设左指针为height[ i ],右指针为height[ j ]。当 height[ i ] < height[ j ] 时，移动左指针，反之，移动右指针。
原因：由于容纳的水量是由
两个指针指向的数字中较小值 * 指针之间的距离
决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。
贴上大佬的理解：
一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。
看文字肯定没有看代码懂得快（文字我自个看的）：
class Solution {
public:
int maxArea(vector<int>& height) {
int Max=0;
int s,len,h;
int i=0,j=height.size()-1;
while(i<j)
{
len=j-i;
h=min(height[i],height[j]);
s=len*h;
Max=max(Max,s);
if(height[i]<height[j])
{
i++;
}
else
{
j--;
}
}
return Max;
}
};
结束！当然这可能不是最优答案。
第五层理解
@Enginer静态力： 每次都移动自己最差的一边，虽然可能变得更差，但是总比不动（或者减小）强，动最差的部分可能找到更好的结果，但是动另一边总会更差或者不变，兄弟们，这不是题，这是人生，逃离舒适圈！！！