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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
https://leetcode.com/problems/trapping-rain-water/
接雨水，双指针。
一开始双指针分别指向头和尾。
每轮循环找出两边最高的bar，这一轮可以确定的容积取决于短的那条，因为无论中间隔着什么，两边的max总能保证可以存下这些水。
1 /** 2 * @param {number[]} height 3 * @return {number} 4 */ 5 var trap = function(height) { 6 var i = 0, j = height.length - 1, res = 0, 7 leftMax = height[i], rightMax = height[j]; 8 while(i <= j){ 9 leftMax = Math.max(leftMax, height[i]); 10 rightMax = Math.max(rightMax, height[j]); 11 if(leftMax > rightMax){ 12 res += rightMax - height[j]; 13 j--; 14 }else{ 15 res += leftMax - height[i]; 16 i++; 17 } 18 19 } 20 return res; 21 };
[LeetCode][JavaScript]Trapping Rain Water
原文：http://www.cnblogs.com/Liok3187/p/4784111.html