42 Trapping Rain Water

题意：

给一个数组，每个值表示一个高度，问这样围出的图形可以盛多少水。

上图是[0,1,0,2,1,0,1,3,2,1,2,1]所围成图形。

思路1：

每个位置可以盛水的量是由左边最高的柱子高度和右边最高的柱子高柱的较小值与当前位子的柱子高度决定的。如图

#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a<b?b:a)
int trap(vector<int>& height) {
	int sz = height.size();
	if (sz < 2)
		return 0;
	//int* left_max = new int[sz];
	//int* right_max = new int[sz];
	vector<int> left_max(sz), right_max(sz);//分别记录i左侧和右侧最高的柱子(包含i)
	left_max[0] = height[0];
	right_max[sz - 1] = height[sz - 1];

	for (int i = 1; i < sz; ++i)
		left_max[i] = MAX(left_max[i - 1], height[i]);
	
	for (int i = sz - 2; i > -1; --i)
		right_max[i] = MAX(right_max[i + 1], height[i]);

	int res = 0;
	for (int i = 1; i < sz-1; ++i)
		res += MIN(left_max[i], right_max[i]) - height[i];
	return res;
}

思路2：

进行优化，从3O(N)降至2O(N)。不分别使用left_max和right_max，而使用record第一次记录左边最大值，第二次记录左右最大值中的较小值，并在得到record的时候就进行当前位置可存水的数量。

int trap(vector<int>& height) {//优化
	int sz = height.size();
	if (sz < 2)
		return 0;
	int* record = new int[sz];
	record[0] = height[0];
	int maxleft = 0, res = 0;
	for (int i = 0; i < sz; ++i) {
		record[i] = maxleft;// [i]位置的大小取决于[i-1]，那么当i==0时，就要给定一个初始值，就是0.记录范围不含i
		maxleft = MAX(maxleft, height[i]);
	}

	int maxright = 0;
	for (int i = sz - 1; i > -1; --i) {
		record[i] = MIN(maxright, record[i]);// 这里record记录的不是右边的最大值，而是：左右最大值中的较小值，就是为了找到关键的threshold。
		// 而右边的最大值只需要通过一个参数来记录即可，因为scan过这一遍后，就得到结果了，没必要保存每个位置的右最大值。
		maxright = MAX(maxright, height[i]);
		if (record[i] > height[i])
			res += record[i] - height[i];
	}
	return res;
}