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.

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

C code:

```void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void waterCal(int** height, const int left, const int right, int* water) { if(right - left < 2) return;```

int first = 0, second = 0;
int newLeft = 0, newRight = 0;
for(int i = left; i <= right; ++i)
{
if((*height)[i] >= first) { second = first; first = (*height)[i]; newRight = newLeft; newLeft = i; }
else if((*height)[i] < first && (*height)[i] >= second) { second = (*height)[i]; newRight = i; }
}
if(newLeft > newRight) swap(&newLeft, &newRight);
int minHeight = second;
for(int i = newLeft + 1; i < newRight; ++i)
*water += second – (*height)[i];
waterCal(height, left, newLeft, water);
waterCal(height, newRight, right, water);
}

int trap(int* height, int heightSize) {
int water = 0;
waterCal(&height, 0, heightSize – 1, &water);
return water;
}

C++

```class Solution { public: void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void waterCal(vector<int>& height, const int left, const int right, int& water) { if(right - left < 2) return;```

int first = 0, second = 0;
int newLeft = 0, newRight = 0;
for(int i = left; i <= right; ++i)
{
if(height[i] >= first) { second = first; first = height[i]; newRight = newLeft; newLeft = i; }
else if(height[i] < first && height[i] >= second) { second = height[i]; newRight = i; }
}
if(newLeft > newRight) swap(newLeft, newRight);
int minHeight = second;
for(int i = newLeft + 1; i < newRight; ++i)
water += second – height[i];
waterCal(height, left, newLeft, water);
waterCal(height, newRight, right, water);
}

int trap(vector<int>& height) {
int water = 0;
waterCal(height, 0, height.size() – 1, water);
return water;
}
};