2021/3/25 直方图的水量

题目描述

描述转载自力扣《面试题 17.21. 直方图的水量》
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

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

示例

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

解题思路

1. 其实不难，每个格子能装的水量本质就是木桶效应，比较左边和右边哪根柱子最低，然后用最低的那个值减去自己这根柱子的高度，当然，减去之后的值不能为负数，否则就是不能装水的意思。
2. 从左往右扫描，记录当前元素左边的最高的柱子。从右往左扫描，记录当前元素右边最高的柱子。
3. 按照（1）的步骤计算。左边最高和右边最高的柱子哪根比较短，就用哪根减去当前的柱子高度，且不小于0。

Java代码实现

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (len <= 2) return 0;    // 只有两根柱子，必然接不住水
        int[] leftMax = new int[len];    // 记录当前格子左边最高的柱子
        leftMax[0] = Integer.MIN_VALUE;    // 第一个格子左边没柱子，可设为负无穷
        int[] rightMax = new int[len];    // 记录当前格子右边最高的柱子
        rightMax[len - 1] = Integer.MIN_VALUE;    // 最后一个格子右边没柱子，可设为负无穷
        for (int i = 1; i < len; ++i) {    // 从左往右遍历，记录左边最高柱子
            leftMax[i] = height[i - 1] > leftMax[i - 1] ? height[i - 1] : leftMax[i - 1];
        }
        for (int i = len - 2; i >= 0; --i) {    // 从右往左遍历，记录右边最高柱子
            rightMax[i] = height[i + 1] > rightMax[i + 1] ? height[i + 1] : rightMax[i + 1];
        }

        int res = 0;
        for (int i = 1; i < len - 1; ++i) {
            // 左右两个柱子只要其中一个比当前柱子还要低，那就注定接不了水，跳过这个格子
            if (leftMax[i] < height[i] || rightMax[i] < height[i]) continue;
            // 左右两个柱子，因为木桶效应，最多只能接短的那一边 
            int minVal = leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i];
            // 计算总和
            res += minVal - height[i];
        }
        return res;
    }
}