题目大意,给n个点,在一个数轴上。每个点对x轴作垂线,找出由两条垂线和X轴组成的一个“容器”的装的水面积最大。就是两条垂线较小的高度*两垂线高度的面积最大。 1、暴力做法 两两遍历。显然是会超时的 2、思路一 从左到右,找出以每一个点所在的垂线作为较矮的高度时候的最大面积,把每个点的垂线作为最大面积一一比较即可。也就是一个点分别往左扫和往右扫。
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let maxarea = 0
const length = height.length;
for (let i = 0;i < length;i++){
let leftarea = 0,rightarea = 0,lj = 0,rj = length - 1;
while(lj < i){
if (height[lj] >= height[i]){
//往左扫到那条边比原来基准边大就可以停止扫了,因为再往左也没意义了
leftarea = (i - lj) * height[i];
break;
}
lj ++;
}
while(rj > i){
if (height[rj] >= height[i]){
//同理
rightarea = (rj - i) * height[i];
break;
}
rj --;
}
maxarea = Math.max(leftarea,rightarea,maxarea)
}
return maxarea
};
这样的效率虽然比暴力好一点能够通工leetcode的测评,但是效率还是很低的,只超过了百分之5的人。思路一之所以效率低,是因为有些情况下我们是做了重复的工作的。例如我以高度为4为矮边去扫到了1条高度为3的边。但是因为4是矮,所以会忽略了3的那次。然而实际上可能以那条3为矮的边与4组成的结果是更优的,而我们要到下次遍历到高度为3的那条边时才会去计算,而且思路2的方法的向左向右扫是会有不必要的重合的
思路2。 我又换了一种思路: 左侧断点和右侧断点同时开始扫,左右分别用两个东西标记一下。如果左边的垂线高度小于右边的,则左边的标记往右一位(这样才能找出更大的);同理右边的垂线高度小于左边的,则右边
var maxArea2 = function(height) {
let maxarea = 0
const length = height.length;
let left = 0,right = length - 1;
while (left < right){
let area = Math.min(height[left],height[right]) * (right - left);
maxarea = Math.max(area,maxarea);
if (height[left] < height[right]){
left ++;
}else{
right --;
}
}
return maxarea
};
这种算法就优于百分之80的了。