侧边栏壁纸
博主头像
日常事博主等级

行动起来,活在当下

  • 累计撰写 67 篇文章
  • 累计创建 16 个标签
  • 累计收到 22 条评论

目 录CONTENT

文章目录

【每日一题】直方图的水量

Administrator
2021-04-04 / 0 评论 / 3 点赞 / 1059 阅读 / 1089 字

给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 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

暴力破解:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
	//从1遍历到n-1的位置是因为左右均无护栏,不能存水!
        for (int i = 1; i < n - 1; i++) {
            int cur = height[i];

            //获取当前位置的左边最大值
            int l = Integer.MIN_VALUE;
            for (int j = i - 1; j >= 0; j--) l = Math.max(l, height[j]);
            if (l <= cur) continue;

            //获取当前位置的右边边最大值
            int r = Integer.MIN_VALUE;
            for (int j = i + 1; j < n; j++) r = Math.max(r, height[j]);
            if (r <= cur) continue;

            //计算当前位置可接的雨水,左右最大值间最小值减当前高度为当前位置可装的水量
            ans += Math.min(l, r) - cur;
        }
        return ans;
    }
}
3

评论区