捕获雨水高程是数组

Question

我在一份试卷中解决了这个问题，并在答案书中找到了一个解决方案。我无法理解其背后的算法。谁能解释一下这个算法是如何工作的？

给定 n 个非负整数表示海拔图，其中每个条形的宽度为 1，计算下雨后它能够捕获多少水。

例如，给定输入

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

返回值将是

6

根据答案书的解决方案是这样的

public class Solution {
    public int trap(int[] height) {
        if (height.length <=2 )
            return 0;
        int h = 0, sum = 0, i = 0, j = height.length - 1;
        while(i < j)
        {
            if ( height[i] < height[j] )
            {
                h = Math.max(h,height[i]);
                sum += h - height[i];
                i++;
            }
            else
            {   
                h = Math.max(h,height[j]);
                sum += h - height[j];
                j--;
            }
        }
        return sum;
    }
}

谢谢

Answer 1

WoDoSc很友善地绘制了海拔和滞留水的图表。水只能被困在两个较高海拔之间。

我所做的就是运行代码并输出结果，以便您可以看到截留的水是如何计算的。代码从“山”范围的两端开始。较低的一端会移近中心。

在两端高度相同的情况下，右端向中心靠拢。您可以将左端移至更靠近中心的位置。

第一列是左侧标高的高度和索引。第二列是右侧标高的高度和索引。

第三列是最大最小高度。换句话说，左侧或右侧的最大高度，以较小者为准。这个数字对于确定当地水位很重要。

第四列是总和。

按照图表，您可以看到算法是如何工作的。

0,0   1,11   0   0
1,1   1,11   1   0
1,1   2,10   1   0
0,2   2,10   1   1
2,3   2,10   2   1
2,3   1,9    2   2
2,3   2,8    2   2
2,3   3,7    2   2
1,4   3,7    2   3
0,5   3,7    2   5
1,6   3,7    2   6

6

这是代码。将 print 和 println 语句放在适当的位置可以帮助您了解代码的作用。

package com.ggl.testing;

public class RainWater implements Runnable {

    public static void main(String[] args) {
        new RainWater().run();
    }

    @Override
    public void run() {
        int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        System.out.println(trap(height));
    }

    public int trap(int[] height) {
        if (height.length <= 2) {
            return 0;
        }

        int h = 0, sum = 0, i = 0, j = height.length - 1;

        while (i < j) {
            System.out.print(height[i] + "," + i + "   " + height[j] + "," + j
                    + "   ");

            if (height[i] < height[j]) {
                h = Math.max(h, height[i]);
                sum += h - height[i];
                i++;
            } else {
                h = Math.max(h, height[j]);
                sum += h - height[j];
                j--;
            }

            System.out.println(h + "   " + sum);
        }

        return sum;
    }

}