diff options
Diffstat (limited to 'trapping_rain_water.c')
-rw-r--r-- | trapping_rain_water.c | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/trapping_rain_water.c b/trapping_rain_water.c new file mode 100644 index 0000000..594efc1 --- /dev/null +++ b/trapping_rain_water.c @@ -0,0 +1,29 @@ +// 42. Trapping Rain Water +#include "leetcode.h" + +/* + * given 'n' non-negative integers representing an elevation map where the width + * of each bar is 1, compute how much water it can trap after raining. + */ + +int trap(int *height, int heightSize) { + int *left = (int *)malloc(heightSize * sizeof(int)); + int *right = (int *)malloc(heightSize * sizeof(int)); + left[0] = height[0]; + right[heightSize - 1] = height[heightSize - 1]; + for (int i = 1; i < heightSize; i++) + left[i] = height[i] > left[i - 1] ? height[i] : left[i - 1]; + for (int i = heightSize - 2; i >= 0; i--) + right[i] = height[i] > right[i + 1] ? height[i] : right[i + 1]; + int ans = 0; + for (int i = 0; i < heightSize; i++) + ans += (fmin(left[i], right[i]) - height[i]); + free(left), free(right); + return ans; +} + +int main() { + int h1[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}, h2[] = {4, 2, 0, 3, 2, 5}; + printf("%d\n", trap(h1, ARRAY_SIZE(h1))); // expect: 6 + printf("%d\n", trap(h2, ARRAY_SIZE(h2))); // expect: 9 +} |