mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 07:29:47 +08:00
62 lines
1.4 KiB
JavaScript
62 lines
1.4 KiB
JavaScript
/**
|
|
* @param {number[]} height
|
|
* @return {number}
|
|
*/
|
|
|
|
/* 42. Trapping Rain Water
|
|
https://leetcode.com/problems/trapping-rain-water/
|
|
|
|
Helpful animation of this prompt: https://youtu.be/HmBbcDiJapY?t=51
|
|
|
|
Given n non-negative integers representing an elevation map where
|
|
the width of each bar is 1, compute how much water it is able to trap
|
|
after raining.
|
|
|
|
VIEW ELEVATION MAP ON LEETCODE
|
|
|
|
Example:
|
|
|
|
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
|
|
Output: 6
|
|
|
|
Plan:
|
|
iterate through and find left maxes
|
|
iterate through and find right maxes
|
|
create minheight and assign it to the min(leftmax, rightmax)
|
|
if current height(element) < minheight
|
|
push minheight - height into water array
|
|
else
|
|
push 0 onto water array
|
|
|
|
sum up water array and return
|
|
|
|
left maxes = [0,0,1,1,2,2,2,2,3,3,3,3]
|
|
right maxes = [3,3,3,3,3,3,3,2,2,2,1,0]
|
|
water contained = [0,0,1,0,1,2,1,0,0,1,0,0] -> sum = 6
|
|
*/
|
|
|
|
export const trap = (heights) => {
|
|
const maxes = new Array(heights.length).fill(0)
|
|
|
|
let leftMax = 0
|
|
for (let i = 0; i < heights.length; i++) {
|
|
const height = heights[i]
|
|
maxes[i] = leftMax
|
|
leftMax = Math.max(leftMax, height)
|
|
}
|
|
|
|
let rightMax = 0
|
|
for (let i = heights.length - 1; i >= 0; i -= 1) {
|
|
const height = heights[i]
|
|
const minHeight = Math.min(rightMax, maxes[i])
|
|
|
|
if (height < minHeight) {
|
|
maxes[i] = minHeight - height
|
|
} else {
|
|
maxes[i] = 0
|
|
}
|
|
rightMax = Math.max(rightMax, height)
|
|
}
|
|
return maxes.reduce((a, b) => a + b, 0)
|
|
}
|