題目
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.
一個(gè)非負(fù)的整數(shù)數(shù)組袋毙，元素大小代表柱子高度墩虹，每個(gè)柱子寬度1，返回這些柱子能夠收集到的雨水體積
volume.png
上面圖片對(duì)應(yīng)的是數(shù)組： [0,1,0,2,1,0,1,3,2,1,2,1]
其藍(lán)色部分就是收集到的雨水的體積： 6
- 解法
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
const len = height.length
let maxX = 0
// 找到最高的那個(gè)柱子
for(i = 0; i < len; i++){
maxX = height[i] > height[maxX] ? i : maxX
}
// 記錄體積
let volume = 0
// 從左往右到最高柱子雨水能收集到的體積
let lp = 0 //用來(lái)保存左邊最高的柱子
for(let i = 0; i < maxX; i++){
if(height[i] > lp){
lp = height[i]
}else{
// 關(guān)鍵理解這一步婶芭，比如柱子A高3，下一個(gè)柱子高2挥吵，那么他們的差距1就是能收集到的雨水
volume += lp - height[i]
}
}
// 從右往左遍歷到最高柱子能夠收集到的雨水
let rp = 0
for(let i = len -1; i > maxX; i--){
if(height[i] > rp){
rp = height[i]
}else{
volume += rp - height[i]
}
}
return volume
}
- 思路分析
找到數(shù)組最高的柱子
然后從左邊和右邊分別求出雨水體積
關(guān)鍵結(jié)合圖形思考
