主题说明
现有 n 个宽度为 1 的柱子，给出 n 个非负整数依次表示柱子的高度，排列后如下图所示，此时均匀从上空向下撒青豆，计算按此排列的柱子能接住多少青豆。（不考虑边角堆积）
以示例图为例，输入数组为[5,0,2,1,4,0,1,0,3],输出为 17 (其他实例也可行 )，下面是我的代码片段，目前已经在码上掘金上发布:
以下为代码链接：
(https://code.juejin.cn/pen/7196213510714425405)
此题思路用了双指针算法,首先要明确，要按照行来计算，还是按照列来计算。我更偏向于列计算：首先，如果按照列来计算的话，宽度一定是1了，我们再把每一列的青豆的高度求出来就可以了。
可以看出每一列青豆的高度，取决于，该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
左侧最高的柱子（用lHeight表示）。
右侧最高的柱子（用rHeight表示）。
本柱子的高度（用height表示）
那么在这个柱子能接的青豆高度为 min(lHeight, rHeight) - height。
青豆高度求出来了，宽度为1，相乘就是的青豆体积了。
此时求出了这个柱子能接的青豆体积。
可以总结为：
- 先定义两个变量来记录左右两端的最大值。
- 从左右两端向中间遍历。
- 如果左右指针指向的值大于对应的最大值，则更新最大值为当前值。
- 否则，计算青豆数量。
- 当左右两个指针为同一位置时，结束循环。
一样的方法，只要从头遍历一遍所有的列，然后求出每一列青豆的体积，相加之后就是总青豆的体积了。
首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接青豆，代码如下：
for (int i = 0; i < height.length; i++) {
// 第一个柱子和最后一个柱子不接青豆
if (i == 0 || i == height.length - 1) continue;
最后，计算该列的青豆高度，代码如下：
int h = Math.min(lHeight, rHeight) - height[i];
if (h > 0) sum += h;
以下为实现主代码
public class Solution {
public int trap(int[] height) {
int sum = 0;
for (int i = 0; i < height.length; i++) {
// 第一个柱子和最后一个柱子不接青豆
if (i == 0 || i == height.length - 1) continue;
int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
for (int r = i + 1; r < height.length; r++) {
if (height[r] > rHeight) rHeight = height[r];
}
for (int l = i - 1; l >= 0; l--) {
if (height[l] > lHeight) lHeight = height[l];
}
int h = Math.min(lHeight, rHeight) - height[i];
if (h > 0) sum += h;
}
return sum;
}
public static void main(String[] args) {
Solution test = new Solution();
int trap = test.trap(new int[]{5, 0, 2, 1, 4, 0, 1, 0, 3});
System.out.println(trap);
}
}
通过控制台输出可得
public static void main(String[] args) {
Solution test = new Solution();
int trap = test.trap(new int[]{5, 0, 2, 1, 4, 0, 1, 0, 3});
System.out.println(trap);
}