1. Runtime Distribution

2. Submission Details

3. Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

4. Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

int trap(int* height, int heightSize) {
	
	int leftMax = *height, rightMax = height[heightSize - 1];
	int i = 0, j = heightSize -1, result = 0;
	while(i <= j)
	{
		while (leftMax <= rightMax && i <= j && height[i] < leftMax) result += leftMax - height[i++];
		if(height[i] >= leftMax)
		{
			leftMax = height[i];
			i++;
		}
		while (rightMax < leftMax && i <= j && height[j] < rightMax) result += rightMax - height[j--];
		if(height[j] >= rightMax)
		{
			rightMax = height[j];
			j--;
		}
	}
	return result;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C" active="active"]

#include
#include

int trap(int* height, int heightSize) {
	
	int leftMax = *height, rightMax = height[heightSize - 1];
	int i = 0, j = heightSize -1, result = 0;
	while(i <= j)
	{
		while (leftMax <= rightMax && i <= j && height[i] < leftMax) result += leftMax - height[i++];
		if(height[i] >= leftMax)
		{
			leftMax = height[i];
			i++;
		}
		while (rightMax < leftMax && i <= j && height[j] < rightMax) result += rightMax - height[j--];
		if(height[j] >= rightMax)
		{
			rightMax = height[j];
			j--;
		}
	}
	return result;
}

int main()
{
 	int bar[] = {2,0,2};
	printf("%d\n", trap(bar,3));
	system("pause");
	return 0;
}

[/restab]
[/restabs]