描述

给定一个非负数组表示一个高度图，其中每一项的宽度都是1，计算这个高度图能装多少水。

例如：输入[0,1,0,2,1,0,1,3,2,1,2,1]，返回为6。

示意图：

示意图

分析

对于每个柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是min(max_left, max_right)-height，所以：

1，从左往右遍历一次，找出每个柱子左边的最大值；

2，从右往左遍历一次，找出每个柱子右边的最大值；

3，再遍历一次，把每个柱子的面积累加；

代码如下：

int trapWater00(int A[], int n)
{
    int *max_left = new int[n]();
    int *max_right = new int[n]();
    
    for (int i=1; i<n; ++i) {
        max_left[i] = max(max_left[i-1], A[i-1]);
        max_right[n-1-i] = max(max_right[n-i], A[n-i]);
    }
    
    int sum = 0;
    
    for (int i=0; i<n; ++i) {
        int height = min(max_left[i], max_right[i]);
        if (height > A[i]) {
            sum += (height-A[i]);
        }
    }
    
    delete[] max_left;
    delete[] max_right;
    
    return sum;
}