Skip to content

Instantly share code, notes, and snippets.

@unilecs
Last active May 2, 2018 16:24
Show Gist options
  • Save unilecs/26f033372e03881c4e6f829052d61af7 to your computer and use it in GitHub Desktop.
Save unilecs/26f033372e03881c4e6f829052d61af7 to your computer and use it in GitHub Desktop.
Get Sum Volume of water
function waterVolume(arr) {
let leftMax = 0, rightMax = 0, volume = 0;
let left = 0, right = 0;
let leftLocalMaxArr = [], rightLocalMaxArr = [];
for(let i=0; i<arr.length; i++) {
left = i;
right = arr.length - 1 - i;
// локальные максимумы слева
if (arr[left] > leftMax) {
leftMax = arr[left];
}
leftLocalMaxArr.push(leftMax);
// локальные максимумы справа
if (arr[right] > rightMax) {
rightMax = arr[right];
}
rightLocalMaxArr.unshift(rightMax);
}
// проходим по всем точкам и находим общий обьем
// обьем точки: разность минимального локального максимума и значение гистограммы
for(let j=0; j<arr.length; j++) {
if (leftLocalMaxArr[j] <= rightLocalMaxArr[j]) {
volume += leftLocalMaxArr[j] - arr[j];
} else {
volume += rightLocalMaxArr[j] - arr[j];
}
}
return volume;
}
let arr = [ 3, 6, 2, 4, 2, 3, 2, 10, 10, 4 ];
console.info(waterVolume(arr));
@LostInKadath
Copy link

В один проход:
https://gist.github.com/LostInKadath/260e23f275a78a21a698882aeb3f16f3
Вдруг кому пригодится на собеседованиях.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment