面试题 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

思路

这题可以遍历每个位置$i$，确定每个位置$i$可以储蓄的水的数量。第$i$个位置可以储蓄的水量，取决于该位置左边的最高柱子的高度和右边最高柱子的高度。只有其左右两边最高位置的柱子高度都大于第$i$个位置的高度，第$i$个位置才能存下水。 代码如下：

public int trap(int[] height) { int sum = 0; for(int i=0;i<height.length;i++){ int l_max = 0; //计算位置i左边最高柱子的高度，可能是自己 for(int j=0;j<=i;j++){ l_max = l_max>height[j]?l_max:height[j]; } int r_max = 0; //计算位置i右边最高柱子的高度，可能是自己 for(int j=i;j<height.length;j++){ r_max = r_max>height[j]?r_max:height[j]; } //计算位置i的存水量，用l_max 和r_max中最小的一个减去位置i的高度， //由于可能是自身，所以最小是0，说明存不了水，也没有问题。 sum += r_max<l_max?(r_max-height[i]):(l_max-height[i]); } return sum; }

优化

上面的代码比较慢，原因在于计算位置$i$的左右最高柱子消耗时间过多，是$O(N^2)$的。优化的话，可以利用前缀和的思想，代码如下：

public int trap(int[] height) { int sum = 0; int[] l = new int[height.length]; //l[i]表示i左边最高柱子高度 int[] r = new int[height.length]; //r[i]表示i右边最高柱子高度 //从左向右遍历，计算l for(int i=0;i<height.length;i++){ if(i==0){ l[i] = height[i]; }else{ l[i] = height[i]>l[i-1]?height[i]:l[i-1]; } } //从右向左遍历，计算r for(int i=height.length-1;i>=0;i--){ if(i==height.length-1){ r[i] =height[i]; }else{ r[i] = height[i]>r[i+1]?height[i]:r[i+1]; } } //计算存水量 for(int i=0;i<height.length;i++){ sum += l[i]>r[i]?(r[i]-height[i]):(l[i]-height[i]); } return sum; }