LeetCode 接雨水

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

上面是由数组 [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

思路分析：
由上图可知，确定水的量首先需要，确定左边的基准、右边的基准，然后就很简单确定存水的量。
我的思路是以左相邻为最基准（左相邻为index-1对应的高度），右边最高为右基准（右边最高为下标index+1到尾端的最大值），然后计算水的量，计算的同时将原来的高度修改为储水后的高度。

class Solution {
public:
	int trap(vector<int>& height) {
		int heightVecSize = height.size();
		int result = 0;//用于储存结果
		//一遍扫描height，且去掉开头和结尾
		for (int index = 1; index < heightVecSize - 1; ++index){
			int afterIndexMax = *max_element(height.begin() + index + 1, height.end());//index之后最高的高度
			if (height[index] < height[index - 1] && height[index] < afterIndexMax){//如果index小于左相邻、右最高
				//获得左相邻、右最高的最小值
				int tempValueHeight = (afterIndexMax > height[index - 1] ? height[index - 1] : afterIndexMax);
				result += tempValueHeight - height[index];//index可承接的水
				height[index] = tempValueHeight;//修改index为接水后的高度
			}
		}
		return result;
	}
};

算法优化：分析不难发现，此算法时间消耗最大的语句就是寻找右最大值。

int afterIndexMax = *max_element(height.begin() + index + 1, height.end());//index之后最高的高度

但是实际情况，可能并不需要每次都进行寻找，
比如上图的三种情况，完全不需要进行重复计算右最高。
下面的算法将对此种情况进行优化。

class Solution {
public:
	int trap(vector<int>& height) {
		int heightVecSize = height.size();
		int result = 0;//用于储存结果
		//一遍扫描height，且去掉开头和结尾
		for (int index = 1; index < heightVecSize - 1; ++index){
			int afterIndexMax = *max_element(height.begin() + index + 1, height.end());//index之后最高的高度
			if (height[index] < height[index - 1] && height[index] < afterIndexMax){//如果index小于左相邻、右最高
				//获得左相邻、右最高的最小值
				int tempValueHeight = (afterIndexMax > height[index - 1] ? height[index - 1] : afterIndexMax);
				while (height[index] < tempValueHeight){//对上图所说的情况进行归纳
					result += tempValueHeight - height[index];//index可承接的水
					height[index] = tempValueHeight;//修改index为接水后的高度
					++index;
				}
			}
		}
		return result;
	}
};

但是时间复杂度还是比较大，下面将采取“空间换取时间”的策略，将右最高保存，这样，就无需进行重复计算。

class Solution {
public:
	int trap(vector<int>& height) {
		int heightVecSize = height.size();
		int result = 0;//用于储存结果
		vector<int> leftIndexMax(heightVecSize, 0);//用于保存index右边最高
		for (int i = heightVecSize - 2; i > 0; --i){//利用类似动态规划的递推进行计算右边最高
			leftIndexMax[i] = max(leftIndexMax[i + 1], height[i + 1]);
 		}
		//一遍扫描height，且去掉开头和结尾
		for (int index = 1; index < heightVecSize - 1; ++index){
			if (height[index] < height[index - 1] && height[index] < leftIndexMax[index]){//如果index小于左相邻、右最高
				//获得左相邻、右最高的最小值
				int tempValueHeight = min(leftIndexMax[index], height[index - 1]);
				while (height[index] < tempValueHeight){//对上图所说的情况进行归纳
					result += tempValueHeight - height[index];//index可承接的水
					height[index] = tempValueHeight;//修改index为接水后的高度
					++index;
				}
			}
		}
		return result;
	}
};

时间复杂度都在o(n)级别，最后优化的算法空间复杂度为o(n)，前面的空间复杂度为常数级别o(1)。