每日算法-直方图的水量.md

每日算法

难度 - > 困难

日期 - > 2021年4月02日

开始时间 - > 12:30

结束时间 - > 13:05

所用时间 - > 35分钟

执行用时 - > 88 ms

内存消耗 - > 38.3 MB

题目

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

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

示例:

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

答案

/**
 * 直方图的水量
 * @author HCY
 * @since 2021/4/2 下午12:33
 * @param height: 直方图的组成
 * @return int
*/
public static int trap(int[] height) {
    int length = height.length;
    int ans = 0;
    for (int i = 1; i < (length - 1); i++) {
        int cur = height[i];
        int l = 0;
        int r = 0;
        for (int j = i; j >= 0; j--) { l = Math.max(l,height[j]); }
        for (int j = i; j < length; j++){ r = Math.max(r,height[j]); }
        ans += Math.min(l , r) - cur;
    }
    return ans;
}