台阶积水问题算法思考

台阶积水算法探讨

关于台阶积水算法思路的梳理。

问题

有一组不同高度的台阶，有一个整数数组表示，数组中每个数是台阶的高度，当开始下雨了（雨水足够多）台阶之间的水坑会积水多少呢？
如下图，可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1]，返回积水量6。

思路梳理

考虑积水量，可以分析每一级台阶会有多少积水。
首先开头和结尾的台阶不会有积水。中间部分的台阶存在积水，那么它的两端肯定有比它要高的台阶。
基于这个思路，设计了算法1；

private static void getwater(int[] orgin){
          int size=orgin.length;
          System.out.println(Arrays.toString(orgin));
          int[] water= new int[size];//每一级台阶积水量
          int left=orgin[0];//左边最高台阶
          int right=0;
          water[0]=0;
          for(int i=1;i<size;i++){
              if(orgin[i]>=left){//如果是目前为止最高台阶，则更新最高台阶高度，同时改台阶积水为0；
                  left=orgin[i];
                  water[i]=0;
              }else{
                  right=orgin[i];
                  for(int j=i;j<size;j++){//找出右边最高台阶
                      if(orgin[j]>right){
                          right=orgin[j];
                      }
                  }
                  if(right>orgin[i]) {右边最高台阶高于当前台阶，当前台阶积水，否则积水为0；
                      int result = left > right ? right : left;
                      water[i]=result-orgin[i];
                  }else{
                      water[i]=0;
                  }
              }
          }
          System.out.println(Arrays.toString(water));
      }

通过对算法1的求解过程进行反推，发现有大量的重复工作在查询右边最高台阶上，基于性能的考虑，对算法1进行修改得到算法2：

private static void getwater2(int[] orgin){
          int size=orgin.length;
          System.out.println(Arrays.toString(orgin));
          int[] water= new int[size];
          int maxNum=0;
          for(int i=0;i<size;i++){//第一次遍历得到最高台阶高度
              if(orgin[i]>maxNum){
                  maxNum=orgin[i];
              }
          }
          for(int i=0;i<size;i++){//初始化积水统计数组
              water[i]=maxNum-orgin[i];
          }
          int left=orgin[0];
          if(water[0]>0){//不是开头最高
              water[0]=0;
              for(int j=1;j<size&&orgin[j]<maxNum;j++){
                  if(orgin[j]>=left){
                      left=orgin[j];
                      water[j]=0;
                  }else{
                      water[j]=left-orgin[j];
                  }
              }
          }
          int right=orgin[size-1];
          if(right>0){//不是结尾最高
              water[size-1]=0;
              for(int j=(size-2);j<size&&orgin[j]<maxNum;j--){
                  if(orgin[j]>=right){
                      right=orgin[j];
                      water[j]=0;
                  }else{
                      water[j]=right-orgin[j];
                  }
              }
          }
           System.out.println(Arrays.toString(water));
      }

每一级台阶积水最多是最高一级台阶高度减去当前台阶高度。用这个值初始化积水数组可用避免最高级台阶数不止一个时的遗漏。然后分别从左端和右端求每一级台阶的积水量，最终只会遍历数组两次，时间复杂度为O(n),而算法1 的时间复杂度是O(n2).