题解 | #接雨水问题#

接雨水问题

http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

接雨水问题

描述

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

示例1

输入：[3,1,2,5,2,4]

返回值：5

说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水，如题面图。

方法一

思路分析

分析：如果柱子数量小于等于2，那么雨水量为0。分析有意义的情况：

最左侧柱子上的雨水与最右侧柱子上的雨水均为0；
除了两端柱子，中间柱子的雨水量可以表示为柱子m左侧柱子的最大值（包括m）与柱子m左侧柱子的最大值中的较小值减去m
因此问题转换为寻找柱子左侧与右侧柱子的较小值

方法一中使用遍历的办法从前往后寻找左侧柱子中的最大值，与右侧柱子中的最大值。

图解

核心代码

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
       long n = arr.size();
        if (n<=2)//只有两个位置，雨水为0
        {
            return 0;
        }
        long sum = 0;
		for(int i=1;i<n-1;i++)//跳过左端和右端
		{
            int max_left=arr[0];//左侧位置的最大值
		    int max_right=arr[n-1];//右侧位置的最大值
            int j=0;
		    while(j<=i)//记录当前位置左侧的最大值
            {
                max_left=max(max_left,arr[j]);
                j++;
            }
            int k=i;
		    while(k<n)
			{
				max_right=max(max_right,arr[k]);//寻找当前记录右侧的最大值
                k++;
			}
            sum+=min(max_left,max_right)-arr[i];//每一个位置的雨水量
		}
        return sum;
     }
};

复杂度分析

时间复杂度：循环遍历数组，在每一位置上还需遍历数组找最大值，因此总的时间复杂度为$O(n^2)$
空间复杂度：空间复杂度为$O(1)$.,

方法二

思路分析

不同方法在于求解左侧柱子的最大值与右侧柱子的最大值，因此可以利用动态规划的思想，设置二维数组rain_arr[n][2]，其中rain_arr[n][0]记录当前为位置下左侧柱子的最大值，根据动态规划的思想，在求解左侧位置的柱子最大值时从左往右计算。rain_arr[n][1]记录当前为位置下右侧柱子的最大值，根据动态规划的思想，在求解右侧位置的柱子最大值时从右往左计算。对应的转移方程如下：

$rainarr[i][0]=max\{rainarr[i-1][0],arr[i]\}$

$rainarr[j][1]=max\{rainarr[j+1][1],arr[j]\}$

核心代码

import java.util.*;

public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int  n = arr.length;
        if(n <= 2)  return 0;
        long sum = 0;
        int[][] rain_arr=new int[n][2];
        for (int i=0; i<n;i++)
        {
            if(i==0) rain_arr[0][0] = arr[0];
            else rain_arr[i][0] = Math.max(rain_arr[i - 1][0], arr[i]);//存储左侧柱子的最大值
        }
        for (int j=n-1; j>=0;j--)
        {
            if(j==n-1)  rain_arr[n-1][1] = arr[n-1];
            else rain_arr[j][1] = Math.max(rain_arr[j + 1][1], arr[j]);//存储右侧柱子的最大值
        }
        for (int i =0; i<n; i++)
        {
            sum += Math.min(rain_arr[i][0], rain_arr[i][1])-arr[i];//计算雨水
        }
       return sum;
    }
    
}

复杂度分析

时间复杂度：时间花费在求解左侧柱子的最大值与右侧柱子的最大值，分别变量两次数组，之后遍历数组求解每个位置的雨水，因此总的时间复杂度为 $O(n)$
空间复杂度：设置二维数组存储信息，空间复杂度为$O(n)$

方法三

思路分析

方法二中需要两次遍历数组（从前往后和从后往前），那么是否可以设置两个指针，分别从开始位置和结束位置开始，向右和向左寻找柱子最大值。方法三思路如下：

设置左指针left从1开始，右指针right从n-1出发
设置max_left表示left左侧柱子的最大值，max_right表示right右侧柱子的最大值。
遍历整个数组，如果左侧最大值小于右侧（max_left<max_right），left位置左右两侧柱子的最大值的较小值可以确定，left右移
否则right位置左右两侧柱子的最大值的较小值可以确定,计算雨水量，right左移

图解

核心代码

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
       long n = arr.size();
        if(n<=2) return 0;
        long res = 0;
        int max_left = arr[0], max_right = arr[n-1];
        int left = 0, right = n-1;
        while (left<right){
            max_left = max(arr[left],max_left);
            max_right = max(arr[right],max_right);
            if(max_left<max_right)//左侧最大值小于右侧，left位置左右两侧柱子的最大值的较小值可以确定，left右移
            {
                res += max_left-arr[left];//计算当前位置的雨水
                left++;
            } 
			else//左侧最大值大于右侧， right位置左右两侧柱子的最大值的较小值可以确定,计算雨水量，right左移           
                       {
                res += max_right-arr[right];//计算当前位置的雨水
                right--;
            }
        }
        return res;
     }
};

复杂度分析