给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6 题解：参考大神写的 某一个柱子能否存储水，判断的准则是左侧柱子最大高度、右侧柱子最大高度的较小值是否高于柱子本身，差值为正即可存储水，避免使用辅助空间，先找到数组中的最高点。该点将数组分为左右两半。对于左半侧，从左向右处理；对于右半侧，从右向左处理。处理的时候只需考虑已扫描一侧的高度即可，因另一侧有数组最高点，无需担心蓄水问题。
public class Solution { public int trap(int[] height) { if(height==null||height.length<3){ return 0; } int n=height.length; //寻找最高的板子 int highest=0; int highestIndex=0; for(int i=0;i<n;i++){ if(highest<height[i]){ highest=height[i]; highestIndex=i; } } int total=0; //从左边找相对较高的位置 for(int i=0,top=0;i<highestIndex;i++){ if(height[i]>=height[top]){ //左侧相对相告的位置 top=i; }else{ total+=height[top]-height[i]; } } for(int i=n-1,top=n-1;i>highestIndex;i--){ if(height[i]>=height[top]){ top=i; }else{ total+=height[top]-height[i]; } } return total; } }