Open sisterAn opened 3 years ago
// 获取最大高度
function getMaxHeight(array) {
let maxHeight = 0;
array.forEach((element) => {
if (element > maxHeight) maxHeight = element;
});
return maxHeight;
}
// 获取正数,可以设置默认值
function getPositiveNumber(number, def) {
return number < 0 ? (def ? def : 0) : number;
}
function trap(height) {
if (lenght === 0) return 0;
let total = 0;
for (let i = 0; i < lenght; i++) {
const leftMax = getMaxHeight(height.slice(0, i));
const rightMax = getMaxHeight(height.slice(i + 1, lenght));
total += getPositiveNumber(Math.min(leftMax, rightMax) - height[i]);
}
return total;
}
function trap(height) {
let total = 0;
let left = 0,
right = height.length - 1,
leftMax = 0,
rightMax = 0;
while (left <= right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
total += leftMax - height[left];
left++;
} else {
total += rightMax - height[right];
right--;
}
}
return total;
}
var trap = function (height) {
let stack = [];
let index = 0;
let sumArea = 0;
while (index < height.length) {
while (stack.length !== 0 && height[index] > height[stack[stack.length - 1]]) {
let h = height[stack[stack.length - 1]];
stack.pop();
if (stack.length === 0) break;
let w = index - stack[stack.length - 1] - 1;
let min = Math.min(height[stack[stack.length - 1]], height[index]);
sumArea += (min - h) * w;
}
stack.push(index);
index++;
}
return sumArea;
};
双指针,中间向两边扩展
var trap = function(height) {
if(height.length <= 1) return 0;
const getMax = (list) => {
if (!list.length) return
let maxIndex = 0
for(let i = 1; i < list.length; i ++) {
if(list[i] > list[maxIndex]) maxIndex = i
}
return maxIndex
}
let maxLeft = maxRight = getMax(height);
let sum = 0;
while(maxLeft > 0) {
let temp = getMax(height.slice(0, maxLeft))
for(let i = temp; i < maxLeft; i ++){
sum += height[temp] - height[i]
}
maxLeft = temp
}
while(maxRight < height.length - 1) {
let temp = getMax(height.slice(maxRight + 1, height.length)) + maxRight + 1
for(let i = maxRight + 1; i < temp; i ++){
sum += height[temp] - height[i]
}
maxRight = temp
}
return sum
};
暴力
var trap = function(height) {
let len = height.length
if(!len)return 0
let sum = 0
for(let i=0;i<len;i++){
let leftA = []
let leftB = []
for(let n=0;n<i;n++){
leftA.push(height[n])
}
for(let n=i+1;n<len;n++){
leftB.push(height[n])
}
let leftMax = leftA.length ? Math.max.apply(null,leftA) : 0
let rightMax = leftB.length ? Math.max.apply(null,leftB) : 0
sum += Math.min(leftMax,rightMax) - height[i] > 0 ? Math.min(leftMax,rightMax) - height[i] : 0
}
return sum
};
这个leetcode 上超时了 优化一下如下
var trap = function(height) {
let len = height.length
if(!len)return 0
let sum = 0
for(let i=0;i<len;i++){
let leftA = []
let leftB = []
let leftMax= -1;
let rightMax = -1
for(let n=0;n<i;n++){
if(height[n] > leftMax){
leftMax = height[n]
}
}
for(let n=i+1;n<len;n++){
if(height[n] > rightMax){
rightMax = height[n]
}
}
sum += Math.min(leftMax,rightMax) - height[i] > 0 ? Math.min(leftMax,rightMax) - height[i] : 0
}
return sum
};
可能用的指针比较多,基本原理也是双指针,做了一个右边双指针为了补全左双指针无法覆盖到的位置,应该有优化的空间
const trap = (height: number[]) => {
const len = height.length;
if (len <= 2) return 0;
let slowLeftPos = 0;
let fastLeftPos = 0;
let slowRightPos = len - 1;
let fastRightPos = len - 1;
let result = 0;
let currentTotalHeight = 0;
while (fastLeftPos < len) {
const slowLeftHeight = height[slowLeftPos];
const fastLeftHeight = height[fastLeftPos];
if (!slowLeftHeight) {
slowLeftPos++;
fastLeftPos++;
continue;
}
if (slowLeftPos === fastLeftPos || slowLeftHeight > fastLeftHeight) {
currentTotalHeight += fastLeftHeight;
fastLeftPos++;
continue;
}
result += (fastLeftPos - slowLeftPos) * slowLeftHeight - currentTotalHeight;
slowLeftPos = fastLeftPos; // 移动左慢指针至左快指针位置
currentTotalHeight = 0;
}
currentTotalHeight = 0; // 重制 currentTotalHeight
while (fastRightPos >= slowLeftPos) {
const slowRightHeight = height[slowRightPos];
const fastRightHeight = height[fastRightPos];
if (!slowRightHeight) {
slowRightPos--;
fastRightPos--;
continue;
}
if (slowRightPos === fastRightPos || slowRightHeight > fastRightHeight) {
currentTotalHeight += fastRightHeight;
fastRightPos--;
continue;
}
result += (slowRightPos - fastRightPos) * slowRightHeight - currentTotalHeight;
slowRightPos = fastRightPos; // 移动右慢指针至右快指针位置
currentTotalHeight = 0;
}
return result;
};
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
示例 2:
提示:
leetcode