描述

• 给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。
  
• 示例1
  输入：[3,1,2,5,2,4]
  返回值：5
  说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水
• 示例2
  输入：[4,5,1,3,2]
  返回值：2
  备注：

方法一

思路

• 暴力遍历
• 可以对每一个位置计算其容水量，这里将每一个下标类比为坑。譬如说，我需要对下标为index的位置计算能够装多少水，我需要找这个坑的左右边界，而它的左右边界实际上就是其左右数据的最大值maxleft以及maxright，,当容量为负数时，记为0，不装水。
• 所以可以遍历数组，计算从1~n的所有坑的容量，总和即为所接雨水的总容量。
• 代码如下：

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // 返回0
        if(arr == null || arr.length < 3){
            return 0;
        }
        // 接水数
        long count = 0;
        int len = arr.length;
        int nextLen = len - 1;
        for (int i = 1;i < nextLen;++i){
            int maxLeft = 0;
            int maxRight = 0;
            // 求左侧最大值
            for (int j = 0;j < i;++j){
                maxLeft = Math.max(arr[j],maxLeft);
            }
            // 求右侧最大值
            for(int m = i + 1;m < len;++m){
                maxRight = Math.max(maxRight,arr[m]);
            }
            // 当前坑的接水数
            int height = Math.min(maxRight,maxLeft) - arr[i];
            count += Math.max(0,height) ;
        }
        return count;
    }
}

• 时间复杂度：，双重循环；
• 空间复杂度：,常数级空间复杂度。

方法二

思路

• 两次遍历，双指针
• 接雨水通俗点说就是找坑，坑的数量以及总容量即为所接雨水的数量，对于递增序列以及递减序列一定是没有坑的，也就是这种序列是接不到雨水的。
• 那么有坑的条件是什么呢？
• 假设某坑的边界是(i,j),那么坑中的数据必然是满足如下条件的：
  
• 对于边界则存在如下三种情况：
  1.
  2.
  3.
• 故可以分两次遍历计算坑的总容量，第一次从左往右遍历，找出满足情况2的坑容量，第二次从右往左遍历找出满足情况1和3的坑容量，两次结果相加即为坑的总容量。
• 参考下图示例：
  
• 代码如下：

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        if(arr == null || arr.length < 3){
            return 0;
        }
        int p = 0;
        int q = 1;
        int len = arr.length;
        long count = 0;
        // 递增序列不考虑
        while(q < len && arr[p] <= arr[q]){
            ++p;
            ++q;
        }
        long temp = 0;
        // 从左往右遍历
        while(q < len){
            // 记录存储雨水量
            if (arr[p] > arr[q]){
                temp = temp + arr[p] - arr[q];
                ++q;
            }else{
                // 避免重复计算，所以这里不记录，在倒序处记录
                if (arr[p] == arr[q]){
                    temp = 0;
                }
                p = q;
                ++q;
                count += temp;
                temp = 0;
            }
        }
        p = len - 1;
        q = len - 2;
        // 递减序列不考虑
        while(q >= 0 && arr[q] >= arr[p]){
            --q;
            --p;
        }
        temp = 0;
        // 从右往左遍历
        while(q >= 0){
            if (arr[p] > arr[q]){
                temp = temp + arr[p] - arr[q];
                --q;
            }else{
                p = q;
                --q;
                count += temp;
                temp = 0;
            }
        }
        return count;
    }
}

• 时间复杂度：，两次一重循环；
• 空间复杂度：，常数级空间复杂度。