解法一
这个题目仔细一分析是这样的步骤：先从最左边找一个值left，如果它右边的值right比它小，那么这个值就能够存水，且存的水量应该是right-left，直到遇到一个right是大于或等于left，则这个right不存水，且将这个right作为新的left，重复上述步骤，直到right到数组末尾为止。
但是将这种思路放在给的例子中都是不通过的，原因就是在那个3的位置作为left时，后面没有能够大于或者等于left的值，导致后面那个水就不能加上去。那为什么出了这样的问题，原因就是我们总是假设left后面总会有一个符合条件的right。
那怎样才能够让left后面总是有符合条件的right呢？因为我们知道right总是应该比left大，那么我们可以先找出数组中的最大值。以它为界限，将数组分成两半。左边是从左到右，而右边是从右到左（因为我们总假设right是比left大的，所有相对而言右边就应该是从右到左）。
进而就有了以下的代码：
public int trap(int[] height) {if (height.length < 3)return 0;int trappedWater = 0, peak = 0, peakHeight = 0, start = 0, end = height.length - 1;//先找出最大值及其下标for (int i = 0; i < height.length; i++) {if (height[i] > peakHeight) {peak = i;peakHeight = height[i];}}while (start < peak) { //左半部分从左往右找int curr = start + 1;while (curr < peak && height[curr] < height[start])trappedWater += height[start] - height[curr++];start = curr;}while (end > peak) { //右半部分从右往左找int curr = end - 1;while (curr > peak && height[curr] < height[end])trappedWater += height[end] - height[curr--];end = curr;}return trappedWater;}
解法二
这个也是里面discuss里面的，但是我至今还不知道为什么可以这样做…。代码如下：
class Solution {public int trap(int[] height) {int[] left=new int[height.length];int[] right=new int[height.length];int[] water=new int[height.length];int max=0;//left max height including current building of each buildingfor(int i=0;i<height.length;i++){if(height[i]>max){max=height[i];}left[i]=max;}max=0;//right max height including current building of each buildingfor(int i=height.length-1;i>=0;i--){if(height[i]>max){max=height[i];}right[i]=max;}int watercount=0;//count water on each buildingfor(int i=0;i<height.length;i++){if(left[i]<right[i]) {water[i]=left[i]-height[i]; }elsewater[i]=right[i]-height[i];watercount+=water[i]; //count the water} return watercount;}
}