题目

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.

一个非负的整数数组，元素大小代表柱子高度，每个柱子宽度1，返回这些柱子能够收集到的雨水体积

volume.png

上面图片对应的是数组： [0,1,0,2,1,0,1,3,2,1,2,1]
其蓝色部分就是收集到的雨水的体积： 6

• 解法

/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
 const len = height.length
 let maxX = 0
 // 找到最高的那个柱子
 for(i = 0; i < len; i++){
   maxX = height[i] > height[maxX] ? i : maxX
 }
 // 记录体积
 let volume = 0
 // 从左往右到最高柱子雨水能收集到的体积
 let lp = 0 //用来保存左边最高的柱子
 for(let i = 0; i < maxX; i++){
   if(height[i] > lp){
     lp = height[i]
   }else{
     // 关键理解这一步，比如柱子A高3，下一个柱子高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
}

• 思路分析

找到数组最高的柱子
然后从左边和右边分别求出雨水体积
关键结合图形思考