题目

有一组高度不同对台阶，由一组整数表示。数组中每个数是台阶的高度。 当开始下雨了，水足够多。台阶之间的水坑会积多少水呢？ 编写一个函数，根据给出的数组计算积水量。 例如下图可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1],返回积水量6.

计算思路：

通过计算每一行的积水量来计算总的积水量。 对于最下面的一层来说，积水量等于从左边第一个不为0的地方开始，到右边第一个不为0的地方结束，中间的0的个数。 因此我们采用算一行，减去一行的形式进行计算。比如题目中的例子可以表示为。

当前第一行：

横轴之上只有2个绿色的格子，计数2个，下移一行。

当前第一行：

横轴之上只有4个绿色的格子，计数4个，下移一行。

当前第一行：

横轴之上没有绿色的格子。

共计6个。

代码如下

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <iostream>
#include <vector>

//每个数减1,返回是否都为0
bool DescreOne(std::vector int>& orgVector)
{
    bool bAllZero= true;
    for(std::size_t i = 0 ; i <  orgVector.size(); i++)
    {
        if(orgVector[i]>0)
        {
            orgVector[i]--;
            bAllZero =false;
        }
    }
    return bAllZero;
}


//左边第一个不为0到右边第一个不为0的数中间一共多少个0
int CountLine(const std::vector int> orgVector)
{
    std::size_t leftNotZeroIndex = 0;
    std::size_t rightNotZeroIndex = orgVector.size();
    //计算左边的坐标
    while(leftNotZeroIndex  < orgVector.size())
    {
        if(orgVector[leftNotZeroIndex]>0)
        {
            break;
        }

        leftNotZeroIndex++;
    }


    //计算右边的坐标
    while(rightNotZeroIndex > 0)
    {
        if(orgVector[rightNotZeroIndex] > 0)
        {
            break;
        }
        rightNotZeroIndex--;
    }

    //数0
    int nCount = 0;
    while( leftNotZeroIndex   < rightNotZeroIndex)
    {
        if(orgVector[leftNotZeroIndex]==0)
        {
            nCount++;
        }
        leftNotZeroIndex++;
    }
    return nCount;
}


int WaterCount(std::vector<int> orgVec)
{
    int nSum = 0;
    int nCount = 0;
    while(true)
    {
        nCount = CountLine(orgVec);
        nSum += nCount;
        if(DescreOne(orgVec))
        {
            break;
        }
    }
    return nSum;
}

int main(int argc,char * argv[])
{
    std::vector<int> sampleVec = {0,1,0,2,1,0,1,3,2,1,2,1};
    std::cout  <<WaterCount(sampleVec)<<  std::endl;
    std::vector<int> sampleVec1 = {0,1,0,2,1,0,1,3,2,1,2,1};
    std::cout << WaterCount(sampleVec1)<<  std::endl;

    std::vector<int> sampleVec2 = {3,2,1,1,2,3};
    std::cout << WaterCount(sampleVec2)  <<std::endl;

    std::vector<int> sampleVec3 = {3,2,1,1,2,3,1,1,4};
    std::cout << WaterCount(sampleVec3) << std::endl;

    std::vector <int> sampleVec4 = {3,2,1,1,1,2,4,1,1,3,2,1};
    std::cout<<  WaterCount(sampleVec4) << std::endl;
    return 0;
}