顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 42] Trapping Rain Water [C] [Runtime : 6 MS]
06/24
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
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;
}6.Test
#include<stdio.h>
#include<stdlib.h>
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;
}
