题目：
给定 n 个非负整数表示每个宽度为 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
分析：
首先我介绍一下我的想法，不是很懂的朋友可以先看一下我的，再看下面给出的另外的方法。
我开辟了一个ch数组记录下来当前位置加上之前所有的柱子的高度和，st数组记录下来当前已经接收到的雨水和，比如在题目中柱子5和7接到了1点雨水，但是在8位置，它接到的雨水中已经包含了5到7了，那么这个时候我就要减去这个重复的雨水。
然后我把当前位置柱子之前的最高的柱子找出来，把他们之间能盛下的雨水（假设他们之间的柱子高度都是0）计算出来，减去他们之间柱子的高度和（这个时候需要用到ch数组），再减去已经计算过的雨水的和（st数组，假设每次计算了雨水之后，雨水的部分变成柱子，这样就好理解了），就是最后的答案。
代码：
1 class Solution { 2 //200ms 5% 3 public int trap(int[] height) { 4 int len=height.length; 5 int res=0; 6 int ch[]=new int[len]; 7 int st[]=new int[len]; 8 st[0]=0; 9 ch[0]=height[0]; 10 for(int n=1;n<len;++n) 11 ch[n]=ch[n-1]+height[n]; 12 for(int n=1;n<len;++n) { 13 int max=0,rain=0; 14 int sta=0; 15 for(int m=n-1;m>=0;--m) { 16 if(max<height[m]) { 17 max=height[m]; 18 sta=m; 19 max=max>height[n]?height[n]:max; 20 rain=max*(n-sta-1)-ch[n-1]+ch[m]-st[n-1]+st[m]>rain?max*(n-sta-1)-ch[n-1]+ch[m]-st[n-1]+st[m]:rain; 21 } 22 } 23 st[n]=st[n-1]+rain; 24 ch[n-1]+=rain; 25 res+=rain; 26 } 27 return res; 28 } 29 }
很明显这是个愚蠢的方法，即使思路很清晰但是并不能给算法带来优化，也就是他时间复杂度就是这么高。
那么下面给出我看了别人代码后写出的另外一种代码：
1 class Solution { 2 public int trap(int[] height) { 3 int res=0; 4 int maxl=0,maxr=0; 5 int stl=0,str=height.length-1; 6 for(int n=0;n<height.length;++n) { 7 if(height[stl]<=height[str]) 8 if(maxl>height[stl]) 9 res+=maxl-height[stl++]; 10 else 11 maxl=height[stl++]; 12 else 13 if(maxr>height[str]) 14 res+=maxr-height[str--]; 15 else 16 maxr=height[str--]; 17 } 18 return res; 19 }
网上很多人代码的样子都是这个形式的，不过我就想问一句大哥们你们抄来抄去你们抄懂了么？不自己写一下都不知道有的地方可以优化，而且自己也不说一下代码的想法，直接co过来真的好吗？我第一次看到这种格式的代码时里面有很多比较绕的地方，是很明显可以进行优化的，但是大部分人都是一样的，真是看起来相当费劲。
这段代码的主要目的是为了找最高的柱子，可以看到他每次都进行左右柱子的比较，哪一个小，哪一个就往中心移动，这个操作是为什么呢？
比如你如果只是从左向右的话，{3,2,1}和{3,2,1,3}这种情况怎么办？你加上了2柱子和3柱子位置的雨水，但是你并不能保证他们是被围住的，比如第一个例子，全部降序排列。
如果从左边和右边同时开始找两边最高的柱子呢？
比如{4,3,5}，小的开始移动就是4，高的就是5它不动，那么不管4怎么加，只要比他小的那也比5小，绝对可以围起来当雨水，如果比4大呢？（重点就在这里）。
{4,6,3,5}这个序列中4小于5，但是4也小于6，那么这个时候，左边的最大值现在是4，他没有围到雨水，只是把左边最大值从0提到了4，现在位置到了6和5比较，5和3怎么比都比5小，所以直接加上他们所围成的雨水就好了，是绝对不存在围不到的情况的。
只要开始了右边的遍历，那么maxr<=maxl，因为最高的柱子被人比下去了，反观左边是一样的。所以不用纠结会不会存在为不到的情况。