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!
此题牛客网讲过但是还是忘记怎么做了 看了一下视频才想起来如下一个数组 左边开始7 3...右边开始 4 5
左边最大值7 右边最大值5 显然这时右侧第二个4的存水量可以确定，是5-4=1 因为因为左边的最大值至少是7 右边最大是5 短板限制在右侧的5.
故计左右两侧的最大值，哪一侧的最大值小就结算哪一侧，两侧同时往中间逼近，O(1)时间可以实现遍历 并得出结果
73 .........4 5
public class Solution { public int trap(int[] height) { if(height==null||height.length==0) return 0; int Lmax=height[0]; int Rmax=height[height.length-1]; int i=1,j=height.length-2; int count=0; while(i<=j){ if(Lmax<=Rmax){ if(height[i]<=Lmax) count+=(Lmax-height[i++]); else Lmax=height[i++]; } else{ if(height[j]<=Rmax) count+=(Rmax-height[j--]); else Rmax=height[j--]; } } return count; } }
