相关疑难解决方法(0)

2D版本中的经典算法问题通常被描述为

给定n个非负整数表示每个柱的宽度为1的高程图,计算下雨后能够捕获的水量.

例如,给定输入

[0,1,0,2,1,0,1,3,2,1,2,1] 

返回值是

6

我用来解决上述2D问题的算法是

int trapWaterVolume2D(vector<int> A) {
    int n = A.size();
    vector<int> leftmost(n, 0), rightmost(n, 0);

    //left exclusive scan, O(n), the highest bar to the left each point
    int leftMaxSoFar = 0;
    for (int i = 0; i < n; i++){
        leftmost[i] = leftMaxSoFar;
        if (A[i] > leftMaxSoFar) leftMaxSoFar = A[i];
    }


    //right exclusive scan, O(n), the highest bar to the right each point
    int rightMaxSoFar = 0;
    for (int i = n - 1; i …