直方图的水量

面试题 17.21. 直方图的水量

题目说明

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例

例1

1 2	输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，发现此题是需要好好理解题目，我们统计蓄水处时，实际上需要讨论每个位置左右大于它的位置，这样需要的时间复杂度较高，所以我们可以通过双指针向中间推进的方法，左右指针只需要算对应方向的蓄水处即可，让我们来看看具体如何实现的吧。

实现

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

        int result = 0;

        //左右指针向中间趋近
        int left = 0;
        int right = n - 1;

        //记录左右遍历过程中遇到的最大值
        int maxLeft = 0;
        int maxRight = 0;

        while (left < right) {
            maxLeft = Math.max(maxLeft, height[left]);
            maxRight = Math.max(maxRight, height[right]);

            //不断寻求当前左指针左边最高处与左指针形成的区域
            //及右指针右边最高处与右指针形成的区域
            if (height[left] < height[right]) {
                result += maxLeft - height[left];
                left++;
            }
            else {
                result += maxRight - height[right];
                right--;
            }
        }

        return result;
    }