算法-盛最多水的容器
1. 题目
给定 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
2. 解题
暴力法 : 主要节省效率的地方第一层for循环的height[i] <= heighest - (i - heighestIndex) 判断中 我们假设 第一个柱子是下标 i = 0 height[i] = 10 ，那么第二个柱子下标 j = 1 height[j] 如果小于等于 10 - (i(1) - j(0)) = 9 那么可以跳出该循环，不做暴力解，因为得不到比第一个柱子更优解。
//盛最多水的容器
public int maxArea(int[] height) {
//记录最高
int heighest = 0;
//记录最高的下标
int heighestIndex = 0;
//记录最大区域
int maxArea = 0;
for(int i = 0; i < height.length - 1; i++){
if(height[i] <= heighest - (i - heighestIndex)){
//如果小于最高 - 下标差 则continue;
continue;
}else{
//记录下标
heighest = height[i];
heighestIndex = i;
}
for(int j = i + 1; j < height.length; j++){
int area = ((height[i] < height[j] ? height[i] : height[j]) * (j - i));
maxArea = maxArea < area ? area : maxArea;
}
}
return maxArea;
}
双指针法 指针 i 从最前往后，指针 j 从最后往前 每次计算面积之后，如果 height[i] 比较小，则 i++ 否则 j– 重点(放弃短的柱子，留下长的柱子)
public int maxArea2(int[] height){
int i = 0, j = height.length - 1;
int maxArea = 0;
while( i != j){
maxArea = Math.max(maxArea,(Math.min(height[i],height[j])) * (j - i));
if(height[i] > height[j]){
j--;
}else{
i++;
}
}
return maxArea;
}
