# Solution in C++

• ``````class Solution
{
public:
int trap(vector<int>& height)
{
if (0 == height.size()) return 0;
int maxIndex = 0, sum = 0;
for (int i = 0; i < height.size(); ++i)
if (height[maxIndex] < height[i])
maxIndex = i;
trap(height, 0, maxIndex, sum);
trap(height, maxIndex, height.size() - 1, sum);
return sum;
}
private:
void trap(vector<int>& height, int lo, int hi, int& sum)
{
if (lo == hi) return;
if (height[lo] >= height[hi])
{
int maxIndex = lo + 1;
for (int i = lo + 1; i <= hi; ++i)
if (height[maxIndex] < height[i])
maxIndex = i;
for (int i = lo + 1; i <= maxIndex; ++i)
sum += height[maxIndex] - height[i];
trap(height, maxIndex, hi, sum);
}
else
{
int maxIndex = hi - 1;
for (int i = hi - 1; i >= lo; --i)
if (height[maxIndex] < height[i])
maxIndex = i;
for (int i = hi - 1; i >= maxIndex; --i)
sum += height[maxIndex] - height[i];
trap(height, lo, maxIndex, sum);
}
}
};

class SolutionB
{
public:
int trap(vector<int>& height)
{
if (0 == height.size()) return 0;
int sum = 0, maxIndex = 0, lo = 0, hi = 0, temp = 0;
for (int i = 0; i < height.size(); ++i)
if (height[maxIndex] < height[i])
maxIndex = i;
lo = hi = maxIndex;
while (0 != lo)
{
temp = lo - 1;
for (int i = lo - 1; i >= 0; --i)
if (height[temp] < height[i])
temp = i;
for (int i = lo - 1; i >= temp; --i)
sum += height[temp] - height[i];
lo = temp;
}
while (hi != height.size() - 1)
{
temp = hi + 1;
for (int i = hi + 1; i < height.size(); ++i)
if (height[temp] < height[i])
temp = i;
for (int i = hi + 1; i <= temp; ++i)
sum += height[temp] - height[i];
hi = temp;
}
return sum;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.