算法13:接雨水方法，一排凹槽可以装多少雨水
//“接雨水”算法:
//vNums中数字代表一系列相邻并排的水槽
//如索引号为"0"和"1"的数字0和1代表这一水槽只有右边，即该水槽无法接到雨水
//而索引号从"1"到"3"的水槽可以接到1个单位的水量...
//求解思路:"滑动窗口"，"一个"水槽"一个"水槽的处理,此处的"一个"代表的是一个大的可以储存水的“凹”处水槽
//水槽柱高
vector<int> vNums{ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
//nRainAll储存水槽可以储存的所有水量
//nIndex计算第一个高度非"0"的水槽
int nRainAll = 0, nIndex = 0;
//找到第一个可以装水的水槽
while (0 == vNums[nIndex])
{
nIndex++;
}
//nOneStart记录当前水槽槽边开始索引号
//nOne记录滑动窗口当前槽边索引位置
//nOneMiddle记录水槽底处，即水槽的"中间"位置，该位置的左边水槽边的高度下降，
//该位置的右端，水槽边的高度上升。
//nOneEnd记录的是最右端水槽边的索引号。
int nOneStart = 0, nOne = 0, nOneMiddle = 0, nOneEnd = 0;
//算法开始
//从第一个非0，即有边的水槽开始"滑动窗口"，寻找每一个可以盛水的水槽
for (int i = nIndex; i < vNums.size(); i++)
{
//nSegSum记录当前水槽可以装的水量
int nSegSum = 0;
//判断该索引位置所代表的水槽边的右侧是否还有水槽边
if (i + 1 < vNums.size())
{
//如果还有水槽边的话，就要将水槽的当前边nOne设置为当前索引值i
//水槽的开始边索引值nOneStart设置为当前边索引值
//水槽的"中部"nOneMiddle也设置为当前索引号
//并设置临时变量nNext，探索当前水槽边的右边是否满足其水槽边小于当前水槽边的条件
//如果满足条件，则一直向右滑动，直到“当前”槽边不再小于其前一个槽边
nOneStart = i;
nOne = i;
nOneMiddle = i;
int nNext = i + 1;
//这里是滑动槽边，直到槽边大于等于“当前”槽边的槽边或槽边被探索完
//这样探索的思路就是:将水槽的左边，即槽边从高到低的所有槽边找到，直到槽边高度开始变大，
//即到达"槽底",到达水槽的最低点，这里定义的水槽"中点"(用nOneMinddle记录其索引值)。
while ((nNext < vNums.size()) && (vNums[nNext] < vNums[nOne]))
{
nOne = nNext;
nNext++;
}
//这里代表的就是找到槽底后跳出来的是因为当前索引"nNext"大于大于其前一个槽边高度，
//即槽边高度开始"上升",所以求槽底的索引号时需要减去1，做减减运算
nNext--;
//这里判断我们找到的槽底的索引值是否与水槽左端的索引值相同，如果相同，则意味着
//该水槽槽底与槽边高度相同，显然无法注水，因此用continue跳出该水槽的运算，
//直接进行下一个水槽的盛水运算；反之，如果不同，说明当前水槽可以盛水(至少目前来看可以，因为
//水槽还得判断水槽右边是否满足槽边高于槽底的要求)，此时我们需要更新槽底索引号nOneMiddle为nNext
if (nNext != nOneMiddle)
{
nOneMiddle = nNext;
}
else
{
continue;
}
//这里表示开始判断水槽右端的高度是否满足水槽边高度高于槽底的盛水要求
//同样，水槽右端需要向右滑动1个单位的窗口
if (nOneMiddle + 1 < vNums.size())
{
//这里首先将右端水槽索引号设置为槽底索引号
nOneEnd = nOneMiddle;
//nNext临时变量指向槽底的下一个槽边
nNext = nOneMiddle + 1;
//同寻找槽底的逻辑:这里以槽底为出发点，在滑动窗口过程中寻找下一个槽边小于等于当前槽边的索引号
while ((nNext<vNums.size()) && (vNums[nNext] > vNums[nOneMiddle]))
{
nOneMiddle = nNext;
nNext++;
}
//到这里就表示寻找到槽边高度开始下降了或者是水槽边被探索完，仍然没有找到开始下降的水槽边
nNext--;
//判断找到的右端是否与槽底索引号相同，相同的话表示该水槽只有左边部分(类似一个木桶只有一半，肯定无法注水)
//反之，若右端索引号与槽底索引号不同，则表示该水槽完整，有左右边，有底(是一个完整的水槽)。
if (nOneEnd != nNext)
{
//这里表示更新右端水槽索引号
nOneEnd = nNext;
//nRain计算装满水的水槽的总体积。
//由木桶原理我们知道，水槽低的那端(左端或者右端)，以及水槽的宽度决定了水槽的容积
int nRain = 0;
//这里表示如果水槽左端低的话，我们的水槽只能装到左端水槽高度的水
//同理，若是右端水槽低的话，装水的最大高度就是右端(低的那端)的水槽的高度
if (vNums[nOneStart] < vNums[nOneEnd])
{
nRain = (nOneEnd - nOneStart + 1)*vNums[nOneStart];
//这里是计算出空水槽所占的体积
//因为我们在计算总体积的时候是按照左右端低的那端的水槽高度来计算的
//因此水槽左右端高的那一端的高度也必须按照低的那端计入体积计算，
//这样才能保证:装满水的水槽的总体积 - 空水槽所占的体积 = 水槽装的水的体积
for (int j = nOneStart; j <= nOneEnd; j++)
{
if (vNums[j] <= vNums[nOneStart])
{
nSegSum += vNums[j];
}
else
{
nSegSum += vNums[nOneStart];
}
}
}
else
{
nRain = (nOneEnd - nOneStart + 1)*vNums[nOneEnd];
for (int j = nOneStart; j <= nOneEnd; j++)
{
if (vNums[j] <= vNums[nOneEnd])
{
nSegSum += vNums[j];
}
else
{
nSegSum += vNums[nOneEnd];
}
}
}
//这里表示将当前水槽装的水的体积存储到总水量中
nRainAll += (nRain - nSegSum);
//更新窗口索引值i
i = nOneEnd - 1;
}
else
{
continue;
}
}
}
}