题解 | #接雨水问题#

接雨水问题

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

题意概述

给定一个整形非负数组，每个值表示一个柱子的高度
数组中元素的极大值之间，即柱子之间形成的凹陷处可接雨水，问按给定数组高度的柱子最多能接多少雨水

方法一：暴力（超时）

思路与具体做法

暴力扫描，两重循环。
第一重循环遍历整个数组，可知当前位置柱子的高度；
第二重循环分别从当前柱子向左向右遍历遇到的最高的柱子，标记其高度为left_max，right_max。
两侧柱子中的最矮高度减去当前柱子高度，即为当前柱子所接雨水量，ans+=当前柱子所接雨水量；

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        unsigned long long size=arr.size(),ans=0;
		for(int i=1;i<size-1;i++){//边界两个柱子无法接雨水，枚举其余所有柱子 
			int left_max=0,right_max=0;//从当前柱子向左向右遍历遇到的最高的柱子 
			for(int j=i;j>=0;j--){
				left_max=max(left_max,arr[j]);//从当前柱子向左遍历遇到的最高的柱子 
			}
			for(int j=i;j<size;j++){
				right_max=max(right_max,arr[j]);//从当前柱子向右遍历遇到的最高的柱子 
			} 
			ans+=min(left_max,right_max)-arr[i];//两侧柱子中的最矮高度减去当前柱子高度，即为当前柱子所接雨水量 
		}
		return ans; 
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O (n^{2})$ ，两重循环遍历整个数组。
空间复杂度： $O (1)$ ，用到了常数个额外空间。

方法二：双指针

思路与具体做法

left指针指向从左到右遍历中的当前元素，right指针指向从右到左遍历中的当前元素，left_max记录从左到右遍历中遇到的最大元素，right_max记录从右到左遍历中遇到的最大元素
双指针分别从两个方向遍历数组
不断对左右指针所指向的最小元素计算接水量
- 若当前方向遍历到的当前元素大于等于最大元素，能更新当前方向遍历到的最大元素
- 若当前方向遍历到的当前元素小于最大元素，则计算当前柱子所能接水量
- 然后当前方向的位置指针移动到下一个位置

class Solution {
public:
    long long maxWater(vector<int>& arr) {
    	unsigned long long left=0,right=arr.size()-1,left_max=0,right_max=0;//left指针指向从左到右遍历中的当前元素，right指针指向从右到左遍历中的当前元素，left_max记录从左到右遍历中遇到的最大元素，right_max记录从右到左遍历中遇到的最大元素 
    	unsigned long long ans=0;
		while(left<right){//双指针分别从两个方向遍历数组 
			if(arr[left]<arr[right]){//左指针指向元素较小时 
				if(arr[left]>=left_max)left_max=arr[left];//若能更新遍历到的最大元素则更新 
				else ans+=left_max-arr[left];//计算当前柱子这一列所能接的雨水 
				left++;//左指针右移 
			}else{//右指针指向元素较小时 
				if(arr[right]>=right_max)right_max=arr[right];//若能更新遍历到的最大元素则更新 
				else ans+=right_max-arr[right];//计算当前柱子这一列所能接的雨水 
				right--;//右指针左移 
			}
		} 
		return ans; 
	}
};