直方图的水量

面试题 17.21. 直方图的水量

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

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

示例:

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

方法一：暴力

对于下标 i ，水能达到的最大高度等于下标 i 两边的最大高度的最小值。下标 i 处能接的水能到达的最大高度减去 height[i]。

对于每个下标 i ，我们直接搜索其左边和右边的最大高度，取其中的最小值减去 height[i]，即是位置 i 能存的水量。

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

        int ans = 0;
        for(int i = 0; i < n; ++i){
            int leftMax = height[i];
            for(int j = i - 1; j >= 0; --j){
                if(height[j] > leftMax){
                    leftMax = height[j];
                }
            }
            int rightMax = height[i];
            for(int j = i + 1; j < n; j++){
                if(height[j] > rightMax){
                    rightMax = height[j];
                }
            }
            ans += Math.min(leftMax, rightMax) - height[i];
        }
        return ans;
    }
}

时间复杂度O(n^2)
空间复杂度O(1)

方法二：动态规划

我们使用两个数组 leftMax 和 rightMax，来存储左侧最小值和右侧最小值。leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i]表示下标 i 及其右边的位置中，height的最大高度。

leftMax[0] = height[0]，rightMax[n - 1] = height[n - 1]。最左边元素左侧没有比它更大的元素，最右边元素右侧没有比它更大的元素。
$$
leftMax[i] = max(leftMax[i - 1], height[i])\ \ \ 1 \leq i \leq n - 1
$$

$$
rightMax[i] = max(rightMax[i + 1],height[i])\ \ \ 0 \leq i \leq n - 2
$$

下标 i 处能接的水量为 min(leftMax[i], rightMax[i]) - height[i] 。

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

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for(int i = 1; i < n; ++i){
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; --i){
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for(int i = 0; i < n; ++i){
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

时间复杂度O(n)
空间复杂度O(n)

方法三：双指针

注意到下标 i 处能接的水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组leftMax 是

从左往右计算，数组rightMax 是从右往左计算，因此可以使用双指针和两个标量代替两个数组。

维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left = 0， right = n - 1，leftMax = 0，rightMax = 0，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。

当指针没有相遇时，进行如下操作：

使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值。
如果 height[left] < height[right]，则必有 leftMax < rightMax,下标 left 处能接的水量等于 leftMax - height[left],将数量加入结果中，left++
如果 height[left] >= height[right]，则必有 leftMax >= rightMax,下标 right处能接的水量等于 rightMax - height[right],将数量加入结果中，right–

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while(left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if(height[left] < height[right]){
                ans += leftMax - height[left];
                ++left;
            }else{
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}

时间复杂度O(n)
空间复杂度O(1)