题目参照：

头条雨水算法问题

第二种解法

感谢陈星涯同学提供了第二种思路，思路的图解如下：

思路：

操作分为以下几步：

  1. 寻找最大值的位置。如图1所示。
  2. 在最大值的左右侧，寻找第二大的值的位置。如图2所示。
  3. 计算左第二大值到最大值和右第二大值到最大值之间能有多少个单位的水，如图3所示。
  4. 分别以左第二大值和右第二大值为最大值，重复2，3，4步，直到计算到最左和最右的位置，如图4所示。

C++代码：

具体的C++代码如下所示

从左到右寻找最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

size_t L2RfindMax(const vector int> & v, size_t nStart, size_t nEnd)
{
    size_t nMaxIndex = nEnd;
    int nMax = v[nStart];
    for (size_t i = nStart; i   nEnd; i++)
    {
        if (v[i] >= nMax)
        {
            nMax = v[i];
            nMaxIndex = i;
        }
    }
    return nMaxIndex;
}

从右到左寻找最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

size_t R2LFindMax(const vector int> & v, size_t nStart, size_t nEnd)
{
    size_t nMaxIndex = nStart;
    int nMax = v[nEnd];
    for (size_t i = nEnd; i > nStart; i--)
    {
        if (v[i] > nMax)
        {
            nMax = v[i];
            nMaxIndex = i;
        }
    }
    return nMaxIndex;
}

计算最大值和第二大值之间能放多少个单位的水。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int calculateOne(const vector int> & v, size_t nStart, size_t nEnd)
{
   int total = 0;
   int nLow = v[nStart] > v[nEnd] ? v[nEnd] : v[nStart];
   for (size_t i = nStart + 1; i   nEnd; i++)
   {
       int nLit = nLow - v[i];
       if (nLit > 0)
       {
           total += nLit;
       }
   }
   return total;
}

计算全部能放多少个单位的水。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

int countAll(const vector int> & v)
{
   size_t nEnd = v.size();
   //寻找最大值的位置
   size_t nMax = L2RfindMax(v, 0, nEnd);
   std::cout   <<  "M:"  <<   nMax  <<   std::endl;
   //计算最大值左边能放多少水
   size_t nSecRight = nMax;
   size_t nSecRightEnd = 0;
   int nTotal = 0;
   while (nSecRight <  nEnd - 1)
   {
       std::cout<<"R:"<<nSecRight<<std::endl;

       nSecRightEnd = L2RfindMax(v, nSecRight + 1, nEnd);
       nTotal += calculateOne(v, nSecRight, nSecRightEnd);

       nSecRight = nSecRightEnd;
   }

   //计算最大值右边能放多少水
   size_t nSecLift = nMax;
   size_t nSecLiftEnd = 0;

   while (nSecLift > 0)
   {
       std::cout  <<  "L:"  <<  nSecLift  <<  std::endl;

       nSecLiftEnd = R2LFindMax(v, 0, nSecLift - 1);
       nTotal += calculateOne(v, nSecLiftEnd, nSecLift);

       nSecLift = nSecLiftEnd;
   }
   return nTotal;
}

主函数

1
2
3
4
5
6

int main()
{
    std::vector<int> vTest1 = {1,3,1,3,5,3,7,2,3,2,6,3,4,2,1};
    int nTotal = countAll(vTest1);
    std::cout<<"total:"<<nTotal<<std::endl;
}