如图，在一个n级台阶（此处10）高低各不同，在下雨后其低矮处将蓄积水量。

写出程序求出对于给定的array[n]其蓄水量的总和。

当时面试时候面试官给过一个提示为O（n2）的暴力求和算法，即对每一个i推算其左、右的最高值，然后选其中小的减去a[i]，sum = sum + a[i];即得结果，然后给的问题是用O(N)求得结果。

#include
     
      using namespace std;int main(){    int a[10] = { 1,4,2,8,3,7,3,5,4,2 }；    int leftMaxNumber = 0;    int rightMaxNumber = 0;    int temp = 0;    int sum = 0;    // 从左到右遍历，注意sum值只求到最大值的左边    for( int i = 0;i != 10;++i ）       {        if( a[i] > leftMaxNumber )          {            leftMaxNumber = a[i];            sum += temp;          }        else            temp += leftMaxNumber - a[i];       }    temp = 0;  // temp复原归零，从右到左遍历    for( int i = n-1;i != 0;--i )       {        if( a[i] > rightMaxNumber )          {            rightMaxNumber = a[i];            sum +=  temp;          }        else            temp += rightMaxNumber - a[i];       }    cout << " the total value is: " << sum << endl;    return 0;}