写点什么

【LeetCode】直方图的水量 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 04 月 02 日

题目

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


示例:


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


输出: 6


代码


public class DayCode {    public static void main(String[] args) {        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};        int ans = new DayCode().trap(height);        int ans1 = new DayCode().trap1(height);        System.out.println("ans is " + ans);        System.out.println("ans1 is " + ans1);    }
/** * 时间复杂度 O (n * n) * 空间复杂度 O (1) * 题目链接: https://leetcode-cn.com/problems/volume-of-histogram-lcci/ * * @param height * @return */ public int trap(int[] height) { int result = 0; int heightLength = height.length; for (int i = 1; i < heightLength - 1; i++) { int maxLeft = 0, maxRight = 0; for (int left = i; left >= 0; left--) { maxLeft = Math.max(maxLeft, height[left]); } for (int right = i; right < heightLength; right++) { maxRight = Math.max(maxRight, height[right]); } result += Math.min(maxLeft, maxRight) - height[i]; }
return result; }

/** * 时间复杂度 O(n) * 空间复杂度 O(n) * 题目链接: https://leetcode-cn.com/problems/volume-of-histogram-lcci/ * * @param height * @return */ public int trap1(int[] height) { int ans = 0; Deque<Integer> stack = new ArrayDeque<>(); int n = height.length; for (int i = 0; i < n; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) { break; } int left = stack.peek(); int currentWidth = i - left - 1; int currentHeight = Math.min(height[left], height[i]) - height[top]; ans += currentWidth * currentHeight; } stack.push(i); }
return ans; }}
复制代码


总结

  • 这是一个经典的面试题目,理解题意之后,可以用多种方法解答。

  • 首先,采取暴力法,找 i 的左右高度边界。然后累加求和。暴力法的时间复杂度是 O(n * n)。

  • 这种情况下,我们可以使用单调栈,来减少遍历的次数,使时间复杂度降低到 O(n)。

  • 坚持每日一题,加油!


发布于: 2021 年 04 月 02 日阅读数: 12
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】直方图的水量Java题解