求一维数组蓄水数

太过爱你忘了你带给我的痛 2022-01-09 22:37 226阅读 0赞

# 1、需求 #

很多程序员在面试的时候，都可能遇到一些逻辑思维/编程题，这样的题目非常有意思。而且非常考验程序员的解题技巧和代码编写能力。我这儿就曾经遇到过一个。

具体需求看图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70][]

# 2、解题思路 #

废话不多数。直接给大家讲解思路：

**1、先找出整个数组中的最大值。**

**2、整个数组就被这个最大值给分成了两个数组。**

**3、左边数组，从左往右遍历，计算每个位置的蓄水数，计算规则是：找到当前位置的左边蓄水的最大高度，当前位置的蓄水数就等于min(leftMaxHeight, maxHeight) - currentHeight**

**4、右边数组，从右往左遍历，计算每个位置的蓄水数，计算规则是：找到当前位置的右边蓄水的最大高度，当前位置的蓄水数就等于min(rightMaxHeight, maxHeight) - currentHeight**

**5、最终把每个位置上的蓄水数加起来即可**

# 3、实际代码实现 #

package com.aura.funny.water;
    
    /**
     * 作者： 马中华   https://blog.csdn.net/zhongqi2513
     * 时间： 2019/6/20 10:33
     * 描述：
     *      求出一个一维数组的蓄水数。数组中的每个位置上的值，就是高度，
     *      如果某个值的左右两边都有比它高的值，那么这个位置就可以蓄水。
     *      蓄水的容量 = max(左边， 右边) - 当前位置的值
     */
    public class WaterArray01 {
    
      public static void main(String[] args) {
    
        //   能蓄水的位置和值：        0,1,2,0,0,2,2,0
        int[] waterArray1 = new int[]{4,3,2,5,6,4,4,7};
        int result1 = findTotalWaterStorage(waterArray1);
        System.out.println("蓄水总量为：" + result1);
    
        //   能蓄水的位置和值：        0,0,0,3,4,1,4,0,1,2,0,0
        int[] waterArray2 = new int[]{2,1,5,2,1,4,1,7,2,1,3,1};
        int result2 = findTotalWaterStorage(waterArray2);
        System.out.println("蓄水总量为：" + result2);
    
        //   能蓄水的位置和值：        0,0,0,3,4,1,4,0,1,2,0,0
        int[] waterArray3 = new int[]{4,1,3,5,3,6,2,1,4,7,2,6,4};
        int result3 = findTotalWaterStorage(waterArray3);
        System.out.println("蓄水总量为：" + result3);
      }
    
      /**
       * 整体思路：
       *  先找到最高点，然后分别从左，和 从右 往这个高点遍历。算出蓄水数
       */
      private static int findTotalWaterStorage(int[] waterArray) {
    
        int totalWater = 0;
    
        // 最高点的值
        int maxHeight = waterArray[0];
        // 最高点的位置
        int maxHeightIndex = 0;
    
        // 找出最高点的位置和值
        for(int i = 1; i<waterArray.length; i++){
          if(maxHeight < waterArray[i]){
            maxHeight = waterArray[i];
            maxHeightIndex = i;
          }
        }
    
        /**
         * 隐性前提： leftHeight  一定小于或者等于  maxHeight
         * 隐性前提： rightHeight 一定小于或者等于  maxHeight
         */
    
        // 从左往右扫描
        int leftHeight = waterArray[0];
        for(int i=1; i<maxHeightIndex; i++){
          // 如果当前遍历的位置是低谷
          if(waterArray[i] < leftHeight){
            totalWater += (leftHeight - waterArray[i]);
          }else{
            // 如果不是低谷，则更换左边的较高位置
            leftHeight = waterArray[i];
          }
        }
    
        // 从右往左
        int rightHeight = waterArray[waterArray.length-1];
        for(int i=waterArray.length-2; i>maxHeightIndex; i--){
          // 如果当前遍历的位置是低谷
          if(waterArray[i] < rightHeight){
            totalWater += (rightHeight - waterArray[i]);
          }else{
            // 如果不是低谷，则更换左边的较高位置
            rightHeight = waterArray[i];
          }
        }
        return totalWater;
      }
    }

这种思路的求解的时间复杂度是：O（N）级别。网上其他的O（N \* LogN）级别都不可取

# 4、执行效果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 1][]

大功告成。！！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70]: /images/20220109/07440708133241d2bf55295714b40f89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 1]: /images/20220109/d2c2c5adba454f1ea1204d66139f6b5c.png