接雨水问题

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
**

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

如图所示，对于某一个具体的位置来说，给定的柱子宽度都是1，因此，该位置可能接的雨水量就只和高度相关。根据木桶盛水的短板原则，位置能接多少水，还取决于它两边的情况。即左边的最大高度和右边的最大高度，并且最多接水量只和两者中最小的高度（）相关。

• 如果，那么位置接水量就是两者的差值
• 如果，那么位置无法接水

如何理解呢？以题目中给的🌰为例：

• 如果当前位置为，那么情况如下所示：

左边最高为0，右边最高为3，当前位置为1。根据上述的原则，该位置无法接水

• 如果当前位置为，情况如下所示：

左边最高为1，右边最高为3，当前位置为1，那么该位置也无法接水

• 如果当前位置为，情况如下所示：

左边最高为2，右边最高为3，当前位置为1。满足上述能接水的原则，因此，该位置接水量为

所以，问题的关键就在于如何找到某一位置的左最高和右最高。

首先，我们来看最直观的方法，即到达一个具体的位置先找和。假设当前位置为，那么只能在它的左半部分找且不包含自身，即：

int max_left = 0;
for(int j = i - 1; j >= 0; j--){
    if(height[j] > max_left){
        max_left = height[j];
    }
}

对应的只能在它的右半部分找且不含自身，即：

int max_right = 0;
for(int j = i + 1; j < height.length; j++){
    if(height[j] > max_right){
        max_right = height[j];
    }
}

当找到了和，按照前面的分析，自然就可以得到该位置的接水量。由于两端不可能接雨水，因此，讨论的范围为。下面逐步的通过图示的方式理解下上述的流程。

• ：当前位置为1，，，接水量为0

• ：当前位置为0，，，接水量为1

• ：当前位置为12，，，接水量为0

• ：当前位置为2，，，接水量为0

• ：当前位置为1，，，接水量为1

• ：当前位置为0，，，接水量为2

• ：当前位置为1，，，接水量为1

• ：当前位置为1，，，接水量为0

• ：当前位置为2，，，接水量为0

通过上述的逐步分析，最终的接水量为6。详细的解题代码如下所示：

/**
 * @Author dyliang
 * @Date 2020/11/10 22:39
 * @Version 1.0
 */
public class _42 {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap4(height));
    }
    public static int trap2(int[] height){
        int sum = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            for(int j = i - 1; j >= 0; j--){
                if(height[j] > max_left){
                    max_left = height[j];
                }
            }
            int max_right = 0;
            for(int j = i + 1; j < height.length; j++){
                if(height[j] > max_right){
                    max_right = height[j];
                }
            }
            int min_one = Math.min(max_left,max_right);
            sum += Math.max(0, min_one - height[i]);
        }
        return sum;
    }
}

仔细分析，这种解法需要每个位置都遍历一次给定的数组找和，时间复杂度为。由于过程中没有使用额外的存储空间，空间复杂度为。

如果详细的走过每一个位置可以发现，和在很多位置上并没有发生改变，如下图黄框所示的位置，每一个框内所有位置的的和都是相同的。如果我们提前将每个位置的和找到并存储起来，那么求接水量的时间复杂度就会下降到。虽然，此时空间复杂度变成了，但是空间换时间是完全可接受的。

那么如何找每个位置的和呢？假设从左往右找，当前遍历到了，那么它对应的取决于和位置对应的，而且的值是两者的最大值。

而数组的值取决于每个位置右半部分的情况，因此需要从右往左遍历，对应的原则是。

详细的解题代码如下：

/**
 * @Author dyliang
 * @Date 2020/11/10 22:39
 * @Version 1.0
 */
public class _42 {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap4(height));
    }
    public static int trap3(int[] height){
        int sum = 0;
        int h = height.length;
        int[] max_left = new int[h];
        int[] max_right = new int[h];
        for (int i = 1; i < h - 1; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = h - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < h - 1; i++) {
            int min_one = Math.min(max_left[i], max_right[i]);
            sum += Math.max(0, min_one - height[i]);
        }
        return sum;
    }
}

上面基于备忘录的方法的时间复杂度和空间复杂度都是，由于总是至少要遍历一遍数组，因此，时间复杂度最低也只能是，那么能否不用额外的存储空间完成呢？仔细分析上面的解法可以发现，对于来说，它只关心它对应的，而不关心曾经出现过的。同样对于来说，也只关心它对应的，而不关心曾经的。因此，我们可以使用两个变量来记录目前最大的和。而两端位置的遍历，可以使用指针和进行记录。

而且对于来说，它对应的是不会在变化的，而此时的却不一定。因为，到对应索引位置之间可能存在更大的值。同样，对于来说，是不会变化的，但是却可能变化。但是，只要成立，即时出现更大的，根据接水的原则可知，它不会影响当前的结果。同理，只要成立，即时出现更大的，同样不会影响当前的结果。

详细的解题代码如下：

/**
 * @Author dyliang
 * @Date 2020/11/10 22:39
 * @Version 1.0
 */
public class _42 {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap4(height));
    }
     public static int trap(int[] height) {
        int sum = 0;
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        while(left <= right){
            // 处理left所指的位置
            if(left_max < right_max){
                // 记录接水量
                sum += Math.max(0, left_max - height[left]);
                // 更新可能的max_left
                left_max = Math.max(left_max, height[left]);
                left++;
             // 处理right所指的位置
            } else {
                // 记录接水量
                sum += Math.max(0, right_max - height[right]);
                // 更新可能的max_right
                right_max = Math.max(right_max, height[right]);
                right--;
            }
        }
        return sum;
    }
}