C++算法：接雨水

class Solution {
public:
int trap(vector& height) {
const int c = height.size();
vector leftMax©, rightMax©;
for (int i = 1; i < c; i++)
{
leftMax[i] = max(leftMax[i - 1], height[i - 1]);
}
for (int i = c - 2; i >= 0; i–)
{
rightMax[i] = max(rightMax[i + 1], height[i + 1]);
}
int iSum = 0;
for (int i = 0; i < c; i++)
{
int iNum = min(leftMax[i], rightMax[i]) - height[i];
if (iNum > 0)
{
iSum += iNum;
}
}
return iSum;
}
};

class Solution {
public:
int trap(vector& height) {
m_c = height.size();
vector vWaterHeight(m_c);
vector<pair<int, int>> vHeightIndex;
for (int i = 0; i < m_c; i++)
{
vHeightIndex.emplace_back(height[i], i);
}
sort(vHeightIndex.begin(), vHeightIndex.end());
int left, right;
left = right = vHeightIndex.back().second;
vWaterHeight[left] = vHeightIndex.back().first;
for (int i = vHeightIndex.size() - 2; i >= 0; i–)
{
const auto& [h, inx] = vHeightIndex[i];
if (inx < left)
{
for (int j = inx; j < left; j++)
{
vWaterHeight[j] = h;
}
left = inx;
}
if (inx > right)
{
for (int j = inx; j > right; j–)
{
vWaterHeight[j] = h;
}
right = inx;
}
}
int iRet = std::accumulate(vWaterHeight.begin(), vWaterHeight.end(), 0)
- std::accumulate(height.begin(), height.end(), 0);
return iRet;
}
int m_c;
};