题目
盛最多水的容器
https://leetcode-cn.com/problems/container-with-most-water/
公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注
描述
难度：中等
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
说明：你不能倾斜容器
输入：[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
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
提示
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104
Solution
暴力解法
解题思路
如何求最多的水
求最多的水，本质上是求两个垂直线在二维坐标轴上组成的面积大小，根据木桶原理，能装多少水取决于它最短的那块木板，设定x，y作为两个线的下标，对应height[x]，height[y]作为对应xy的高度整体最终两个垂直线求得的面积公式为
abs(
y-x) * min(height[x],height[y])
通过暴力双重FOR循环，可以很快解出此题，依次算出每个垂直线跟其他垂直线组成的面积大小，超过当前最大面积则替换，循环完后得出最大面积
CODE
class Solution {
public int maxArea(int[] height) {
// (y-x)* min(ax,ay)
if(height.length <= 1) return 0;
int res = 0;//保存结果
for(int i = 0; i < height.length - 1; i++)//以i为左挡板，从O开始
{
for(int j = height.length - 1; j > i; j--)//以j为右挡板，从height.length - 1开始
{
int L = j - i;//底边长度
int H = Math.min(height[i], height[j]);//对短的板子为高
res = Math.max(res, L * H);//取最大值
}
}
return res;
}
}
复杂度
- 时间复杂度
O(N^2)你有你的双指针，我有我的FOR循环
结果
-
超时，之前还没有超时，现在提交已经显示超时...
双指针
解题思路
我们可以设定两个指针来分别指定整个height的全部，指针x初始指定最左侧坐标，指针y初始指定最右侧坐标
我们需要不断移动指针X或者Y，求取对应XY的面积，直到X指针和Y指针相等则面积计算结束
abs(
y-x) * min(height[x],height[y])
回到我们上面的面积计算公式，其中可以拆解为两部分
- abs(
y-x) - min(
height[x],height[y])
这里面有一个隐藏的条件公式
- 移动X，
X=X+1 - 移动Y，
Y=Y-1
对应abs(y-x)，无论移动X或者Y，对应abs(y-x)的值是不变的
- 移动X，
abs(y-(x+1)) = abs(y-x-1) - 移动Y，
abs((y-1)-x) = abs(y-x-1)
对应min(height[x],height[y])
-
如果移动height[x],height[y]中的最大值，则
min(height[x],height[y])的值可能不变或者变小- 不变，新的最大值 > = 现有最小值
- 变小，新的最大值 < 现有最小值
-
如果移动height[x],height[y]中的最小值，则
min(height[x],height[y])的值可能变小，不变或者变大- 变小，新的最小值 < 现有最小值
- 不变，新的最小值 = 现有最小值
- 变大，新的最小值 > 现有最小值
在既有情况下，选择变大方向是计算更大面积的唯一取法
CODE
class Solution {
public int maxArea(int[] height) {
//长度
int length = height.length ;
//左侧指针
int x = 0 ;
//右侧指针
int y = length - 1;
//最大面积
int res = 0;
while(x!=y){
//取两个指针中最小的高度
int minHeight = Math.min(height[x],height[y]);
//计算res，取最大
res = Math.max(res,(y-x)*minHeight);
//如果x对应的高度 > y对应的高度，则需要移动高度低的指针，即y=y-1
if(height[x]-height[y] > 0){
y = y - 1;
}else{
//对应x对应的高度 <= y对应的高度，则需要移动高度低的指针，即x=x+1
x = x + 1;
}
}
return res;
}
}
复杂度
- 时间复杂度：
O(N)，双指针总计最多遍历整个数组一次 - 空间复杂度：
O(1)，只需要额外的常数级别的空间
结果
执行用时：
5ms, 在所有 Java 提交中击败了46.01%的用户内存消耗：
51.9MB, 在所有Java提交中击败了26.93%的用户
断剑重铸之刃，骑士归来之时
