计算结构中的滞留水

Question

假设我的输入是[1, 4, 2, 5, 1, 2, 3]。然后我们可以创建一个结构如下：

...X...
.X.X...
.X.X..X
.XXX.XX
XXXXXXX
1425123

当所有地方都倒水并允许运行关闭时，它将被困在 'O' 个位置：

...X...
.XOX...
.XOXOOX
.XXXOXX
XXXXXXX
1425123

我们必须找到给定列表中被困的总数 'O'。

我的程序能够给我正确的输出，但是当我运行它针对不同的测试用例，它给了我 memory error。有什么办法可以减少这个程序的 space complexity 吗？

def answer(heights):
    row = len(heights)
    col = max(heights)
    sum = 0
    matrix = [['X' for j in range(i)] for i in heights]
    for i in range(col):
        rainWater = []
        for j in range(row):
            try:
                rainWater.append(matrix[j][i])
            except IndexError:
                rainWater.append('0')
        sum += ''.join(rainWater).strip('0').count('0')
    return sum

print answer([1, 4, 2, 5, 1, 2, 3])

列表数组至少有 1 个元素，最多有 9000 个元素。每个元素的值至少为 1，最多为 100000。

Inputs:
    (int list) heights = [1, 4, 2, 5, 1, 2, 3]

Output:
    (int) 5

Inputs:
    (int list) heights = [1, 2, 3, 2, 1]

Output:
    (int) 0

Answer 1

这可以通过以下方式在线性时间和线性内存要求下解决：

def answer(heights):
    minLeft = [0] * len(heights)
    left = 0
    for idx, h in enumerate(heights):
        if left < h:
            left = h
        minLeft[idx] = left

    minRight = [0] * len(heights)
    right = 0
    for idx, h in enumerate(heights[::-1]):
        if right < h:
            right = h
        minRight[len(heights) - 1 - idx] = right

    water = 0
    for h, l, r in zip(heights, minLeft, minRight):
        water += min([l, r]) - h

    return water

数组 minLeft 和 minRight 分别包含当右侧或左侧有无限大的墙时数组中某处可以支撑水的最高水位。那么在每个指标处，可以容纳的总水量是左侧和右侧支持的水位的最小值 - 地板高度.

这个问题在更高维度上处理这个问题（与图像处理中的分水岭问题相关）：The Maximum Volume of Trapped Rain Water in 3D

Answer 2

你可以用一个循环解决这个问题（下面的例子写在Java）：

public static int trapw(int[] check) {
    int sum = 0, ml = 0, mr = 0, clen = 0;

    if ((clen = check.length-1) <= 1)
        return 0;

    int[] r = new int[clen+1];

    for (int k = 0, lidx = clen; k <= clen; k++, lidx = clen - k) {
        ml = Math.max(ml, check[k]); mr = Math.max(mr, check[lidx]);
        if (k < lidx) {
            r[k] = ml; r[lidx] = mr;
        } else if (lidx == k) {
            // Middlepoint
            r[k] = Math.min(ml, mr); sum += Math.max(r[k] - check[k], 0);
        } else {
            r[k] = Math.max((Math.min(ml, r[k]) - check[k]), 0);
            r[lidx] = Math.max((Math.min(mr, r[lidx]) - check[lidx]), 0);
            sum += r[k] + r[lidx];
        }
    }
    return sum;
}

Answer 3

代码在 c# 中。 O(N) 次，O(1) space。使用两个指针和2个整型变量来跟踪。无法为这个问题找到更优化的方法。

     public int Trap(int[] height) {
    if(height == null || height.Length == 0)
      return 0;
    int max = 0;
    int vol = 0;
    int left = 0;
    int right = height.Length - 1;

    while(left<= right)
    {
        if(height[left] < height[right])
        {
            max = Math.Max(max,height[left]);
            vol = vol + (max-height[left]);
            left++;
        }
        else
        {
            max = Math.Max(max,height[right]);
            vol = vol + (max-height[right]);
            right--;
        }
    }
    return vol;
}

计算结构中的滞留水

Calculate trapped water in a structure

python

optimization

performance

out-of-memory

space-complexity