LeetCode——面试题 17.21. 直方图的水量

LeetCode——面试题 17.21. 直方图的水量

题目描述：

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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 static int trap(int[] height) {int n = height.length;if (n == 0) {return 0;}int ans = 0;int[] num1 = new int[n];//左侧的最大值int[] num2 = new int[n];//右侧的最大值int max1 = height[0];for (int i = 1; i < n; i++) {num1[i] = max1;if (height[i] > max1) {max1 = height[i];}}int max2 = height[n - 1];for (int i = n - 2; i >= 0; i--) {num2[i] = max2;if (height[i] > max2) {max2 = height[i];}}for (int i = 1; i < n - 1; i++) {int res = Math.min(num1[i], num2[i]) - height[i];if (res > 0) {ans += res;}}return ans;}
}

执行结果：