本文主要是介绍trap-直方图的水量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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
Related Topics 栈 数组 双指针
解题思路
演示代码
class Solution {Stack<Integer> stack=new Stack<>();public int trap(int[] height) {if(height==null||height.length==0)return 0;int sum=0;stack.add(height[0]);for (int i = 1; i < height.length-1; i++) {if(height[i]<stack.peek()){sum+=findMin(i,height);}else{stack.pop();stack.add(height[i]);}}return sum;}public int findMin(int i,int[] height){int max=height[i+1];for (int j = i+2; j < height.length; j++) {max=Math.max(max,height[j]);}if(max<=height[i])return 0;return Math.min(stack.peek(),max)-height[i];}
}
效果
info
解答成功:
执行耗时:58 ms,击败了8.87% 的Java用户
内存消耗:38.2 MB,击败了35.00% 的Java用户
这篇关于trap-直方图的水量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
