题解 | #接雨水问题#
接雨水问题
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]记录当前为位置下右侧柱子的最大值，根据动态规划的思想，在求解右侧位置的柱子最大值时从右往左计算。对应的转移方程如下：
核心代码
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;
}
};
复杂度分析
- 时间复杂度：方法三只需要一次遍历数组，时间复杂度为$O(n)$
- 空间复杂度：不需要额外的内存空间，空间复杂度为$O(1)$
