RainWaterTrapOptimal
12345678910111213141516171819202122232425262728293031323334353637
var trap = function(heights) {
let total = 0;
let p1 = 0;
let p2 = heights.length-1;
let maxR = 0;
let maxL = 0;
if (heights.length < 3) {
return 0;
}
for (let i = 0; i < heights.length-1; i++) {
if (heights[p1] <= heights[p2]) {
if (heights[p1] > maxL) {
maxL = heights[p1];
} else {
total += maxL - heights[p1];
}
p1++;
} else {
if (heights[p2] > maxR) {
maxR = heights[p2];
} else {
total += maxR - heights[p2];
}
p2--;
}
}
console.log(total);
return total;
};
//trap([0,1,0,2,1,0,3,1,0,1,2]); //8
//trap([0,1,0,2,1,0,1,3,2,1,2,1]); //6
//trap([5,4,1,2]); //1
trap([6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3]); //83
JavaScript
INFO