/**

  * 思路:

  * 1.确定可装水的区域

  *        区域满足如下条件才可装水:

  *            a. 必须包含至少三堵墙

  *            b. 最左(右)侧的墙的高度必须小于另外一侧

  *            c. 非最外侧的墙的高度一定小于或者等于最外侧墙中最小的高度的墙

  * 2.计算可装水区域内某堵墙可装水的容积volume

  * 3.计算可装水区域内所有墙可装水容积之和

  * 4.计算所有可装水区域容积之和

  *

  * 实现:

  * 1 找出最高墙的位置 iMaxIdx

  * 2 从左至右计算可装水容积 V1 直至第iMaxIdx堵墙

  * 3 从右至左计算可装水容积 V2 直至第iMaxIdx堵墙

  * 4 总的可装水容积:V1+V2

  */

 var aWallH = [2,5,1,2,3,4,7,7,6]; //所有墙的高度

 var iWallW = 1; //墙宽度

 var iWallL = 1; //墙长度

 var iTotalV = 0; //总可装水容积

 var iMaxWallIdx = 0; //最高墙的位置

 var getMaxIdx = function(aO){ //找出最高墙的位置

     var iMax = 0,iIdx = 0;

     for (var i = 0; i < aO.length; i++){

         if (iMax < aO[i]){

             iMax = aO[i];

             iIdx = i;

         }

     }

     return iIdx;

 };

 var calVolume = function(aO,start,end,x,w,l){ //计算可装水容积

     var iLeftH = 0;

     var iAreaV = 0;

     var iTotalV = 0;

     var i = start;

     for (; (x == 1) ? (i <= end) : (i >= end); i = i + x){

         if (iLeftH < aO[i]){

             iLeftH = aO[i];

         } else {

             break;

         }

     }

     for (; (x == 1) ? (i <= end) : (i >= end); i = i + x){

         if (iLeftH > aO[i]){

             iAreaV += (iLeftH - aO[i]) * w * l;

         } else {

             iLeftH = aO[i];

             iTotalV += iAreaV;

             iAreaV = 0;

         }

     }

     return iTotalV;

 }

 iMaxWallIdx = getMaxIdx(aWallH);

 iTotalV += calVolume(aWallH,0,iMaxWallIdx,1,iWallW,iWallL);

 iTotalV += calVolume(aWallH,aWallH.length-1,iMaxWallIdx,-1,iWallW,iWallL);

 console.log(iTotalV);

  /*

   * 第7楼osold发表于 2013-11-01 14:06

   * 这个其实对应图形学里面的一个扫描线填充算法。

   *用那个算法实现比较简单。

   */

 /*

  *

备注：此方法有问题！

 第12楼Kalou发表于 2013-11-01 17:12

  *将n个点按顺序连接成折线，分别计算每2个点之间的高度差，

  *当遇到第一个负数时，表示可能开始收集到水，与后面的数相加，

  *知道大于0，此区间*代表能收集到水。依次类推。例如

  *10块砖的高度分别为[2,5,1,3,1,2,1,7,7,6],

  *此时他们之间的距离分别为 [+3,-4,+2,-2,+1,-1,+6,+0,-1],

  *第一个负数为-4，代表5这里可能开始**收集到水，

  *然后向下遍历，-4+2《=0，-4+2-2《=0，-4+2-*2+1《=0，-4+2-2+1-1《=0，-4+2-2+1-1+6》0，

  *这里终止，代表*收集雨水区域为[5,1,3,1,3,1,7]

  */