Trapping rain water

rainwater.c

#include <stdio.h>

static void
minmax(int height[], int n, int *min, int *max) {
	int i;
	*min = *max = height[0];
	for (i=1;i<n;i++) {
		if (height[i] < *min)
			*min = height[i];
		else if (height[i] > *max)
			*max = height[i];
	}
}

static int
skip_water(int height[], int n, int level, int from) {
	if (from >= n)
		return from;
	while (height[from] <= level) {
		++from;
		if (from >= n)
			return from;
	}
	return from;
}

static int
find_border(int height[], int n, int level, int from) {
	from = skip_water(height, n, level, from);
	if (from >= n)
		return from;
	while (height[from] > level) {
		++from;
		if (from >= n)
			return from; 
	}
	return from;
}

static int
count(int height[], int n, int level) {
	int left = 0;
	int water = 0;
	while ((left = find_border(height, n, level, left)) < n) {
		int right = skip_water(height, n, level, left + 1);
		if (right >= n)
			return water;
		water += right - left;
		left = right;
	}
	return water;
}

int
rainwater(int height[], int n) {
	int min,max;
	int i;
	int water = 0;
	minmax(height, n, &min, &max);
	for (i=min;i<max;i++) {
		water += count(height, n, i);
	}
	return water;
}

int
main() {
	int height[] = { 0,1,0,2,1,0,1,3,2,1,2,1 };
	int n = sizeof(height)/sizeof(height[0]);
	int water = rainwater(height, n);
	printf("%d\n", water);
	return 0;
}

rainwater2.c

#include <stdio.h>

int
rainwater(int height[], int n) {
	int left = -1;
	int right = n;
	int left_height = 0;
	int right_height = 0;
	int water = 0;
	if (n <= 0)
		return 0;
	while (left < right) {
		if (left_height <= right_height) {
			++left;
			int h = height[left];
			if (h < left_height)
				water += left_height - h;
			else
				left_height = h;
		} else {
			--right;
			int h = height[right];
			if (h < right_height)
				water += right_height - h;
			else
				right_height = h;
		}
	}
	return water;
}

int
main() {
	int height[] = { 0,1,0,2,1,0,1,3,2,1,2,1 };
	int n = sizeof(height)/sizeof(height[0]);
	int water = rainwater(height, n);
	printf("%d\n", water);
	return 0;
}

修改数组越界。提交通过。

#include <stdio.h>

int
rainwater(int height[], int n) {
	int left = -1;
	int right = n;
	int left_height = 0;
	int right_height = 0;
	int water = 0;

	while (left < right) {
		if (left_height < right_height) {
			++left;
			if (left >= height.length) break;
			int h = height[left];
			if (h < left_height)
				water += left_height - h;
			else
				left_height = h;
		} else {
			--right;
			if (right < 0) break;
			int h = height[right];
			if (h < right_height)
				water += right_height - h;
			else
				right_height = h;
		}
	}
	return water;
}

int
main() {
	int height[] = { 0,1,0,2,1,0,1,3,2,1,2,1 };
	int n = sizeof(height)/sizeof(height[0]);
	int water = rainwater(height, n);
	printf("%d\n", water);
	return 0;
}