forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
42-Trapping-Rain-Water.js
53 lines (43 loc) · 1.39 KB
/
42-Trapping-Rain-Water.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* https://leetcode.com/problems/trapping-rain-water/
* Time O(N) | Space O(1)
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let [left, right] = [0, height.length - 1];
let [maxLeft, maxRight, area] = [0, 0, 0];
while (left < right) {
const [leftHeight, rightHeight] = getHeights(height, left, right);
const [leftWindow, rightWindow] = getWindows(
height,
left,
maxLeft,
right,
maxRight
);
const isRightGreater = leftHeight <= rightHeight;
if (isRightGreater) {
if (hasNewMax(maxLeft, leftHeight)) maxLeft = leftHeight;
else area += leftWindow;
left++;
}
const isRightLess = rightHeight < leftHeight;
if (isRightLess) {
if (hasNewMax(maxRight, rightHeight)) maxRight = rightHeight;
else area += rightWindow;
right--;
}
}
return area;
};
const hasNewMax = (max, height) => max < height;
const getHeights = (height, left, right) => [height[left], height[right]];
const getWindows = (height, left, maxLeft, right, maxRight) => {
const [leftHeight, rightHeight] = getHeights(height, left, right);
const [leftWindow, rightWindow] = [
maxLeft - leftHeight,
maxRight - rightHeight,
];
return [leftWindow, rightWindow];
};