题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [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 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
题解1：按行来求，一行一行算，先计算出最高的“墙”的高度，然后从最高的那行开始遍历，对于每一行来说，比如第5行（首行是第1行），从左到右遍历一行，如果现在该行某一位置墙的高度大于等于5，我们就记录下来，假设用 l 记录，继续向后遍历，发现又出现一个墙的高度大于等于5的位置，用 r 记录下来，那么我们现在就可以确定，l 和 r之间肯定是低洼，可以蓄水的地方，并且由于我们只关心这一行，因此，蓄水的容量就是 r-l+1 。继续遍历这一行的时候，需要先将左边界 l 重置成 r，即 l = r，下一个低洼，就以该 l 作为新的左边界，同样的方法寻找右边界。
处理完一行之后，行数减1开始处理下一行。
class Solution {
public int trap(int[] height) {
int len = height.length;
if (len <= 2) return 0;
int max = Arrays.stream(height).max().orElseThrow(() -> new IllegalArgumentException());
int count = 0;
for (int h = max; h > 0; h--) {
int l = -1;
int r = 0;
while (r < len) {
if (height[r] >= h) {
if (l != -1) {
count += r - l - 1;
}
l = r;
}
r++;
}
}
return count;
}
}代码解释：l 是否等于-1是用来判断现在是否已经找到了一个左边界了，寻找左边界的过程是用 r 的递增来实现的，r 找到一个边界，就会通知 l ，如果是该行第一个左边界，那么 l 是等于-1的，直接将l = r，r 继续寻找下一个边界，再次找到，又来通知 l ，但是现在发现 l 不等于 -1，说明现在找出来一对左右边界了，可以进行蓄水量计算了，计算完成之后，再将 l 置为 r，指定下一个低洼的左边界，以此类推。
说明：320/322 还是会超时，暴力解法可以不用，但是得会，其实我自己做出来的暴力解法要比这个麻烦，但是整体思路是一致的，贴在这里，留个念想，毕竟是第一次这么接近hard题的全对：
public static int trap(int[] height) {
//首先找到最高的元素，就是循环进行次数
int max = Arrays.stream(height).max().orElseThrow(() -> new IllegalArgumentException());
int len = height.length;
int count = 0;
while (max > 0) {
max--;
//int arr[] = new int[len];
List<Integer> list = new ArrayList<>();
//从上往下
for (int i = 0; i < len; i++) {
/*list.add((height[i] - max + 1) > 0:1 ? 0);*/
if((height[i] - max )>0){
list.add(1);
}else{
list.add(0);
}
}
// System.out.println("第"+max+"次循环： "+list);
//初始化l,r
int l = list.indexOf(1);
int r = l+1;
//System.out.println("初始化的l r"+l+" "+r);
while(r<len){
while(r<len&&list.get(r)==0)
{
r++;
}
// System.out.println("不 "+l+" "+r);
if(r<len) {
count += (r - l - 1);
//System.out.println("count: "+count);
l = r;
r = l + 1;
}
}
}
return count;
}题解2：按列求，没有按行求直观，还需要分成三种其概况讨论。涉及三个墙，当前在求的这列墙，这列墙左边最高和右边最高的墙，当往左右最高的墙中间添水的时候，当列在求的墙能蓄多少水，取决于当列以左最高的墙 和 当列以右最高的墙中较矮的一堵（木桶效应），用较矮的一堵墙减去当前在求列墙的高度就是当前列能够蓄水量。这三堵墙的关系又分成以下三种情况：
左右最高的墙中 较矮的那一堵墙高度 大于正在求的列
计算：
左右最高的墙中 较矮的那一堵墙高度 小于当前在求列的高度
计算：当前列没有蓄水
左右最高的墙中 较矮的那一堵墙高度 等于当前在求列的高度
计算：当前列不会蓄水
总结：只有当前列比左右最大高度中较小的那堵墙矮的时候才会蓄水。
代码实现：
public int trap(int[] heights) {
int totalWater = 0;
// 最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
for (int current = 1; current < heights.length - 1; current++) {
int leftMax = 0;
// 找出左边最高
for (int left = current - 1; left >= 0; left--) {
if (heights[left] > leftMax) {
leftMax = heights[left];
}
}
int rightMax = 0;
// 找出右边最高
for (int right = current + 1; right < heights.length; right++) {
if (heights[right] > rightMax) {
rightMax = heights[right];
}
}
// 找出两端较小的
int minHeight = Math.min(leftMax, rightMax);
// 只有较小的一段大于当前列的高度才会有水，其他情况不会有水
if (minHeight > heights[current]) {
totalWater += minHeight - heights[current];
}
}
return totalWater;
}
题解3：针对上述按照列求，会发现有很多重复计算，主要是在，每次计算一列墙的时候，都需要去计算其左边和右边最高墙的高度，这样实际上每计算一列墙都需要循环遍历一遍整个数组，时间复杂度很大，因此考虑用一种算法实现计算每列墙左边和右边的最高墙的高度，并且通过一边循环就计算出来，用数组max_left(i)表示的就是i列以左墙的最高值，max_right(i)就是i列以右墙的最高值，考虑使用dp ，dp方程：
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);完整的代码实现：
public int trap(int[] heights) {
int totalWater = 0;
int n = heights.length;
// maxLeft[i] 表示位置 i 左侧（不包括 i）的最大高度
int[] maxLeft = new int[n];
// maxRight[i] 表示位置 i 右侧（不包括 i）的最大高度
int[] maxRight = new int[n];
// 计算 maxLeft 数组
for (int i = 1; i < n - 1; i++) {
maxLeft[i] = Math.max(maxLeft[i - 1], heights[i - 1]);
}
// 计算 maxRight 数组
for (int i = n - 2; i >= 0; i--) {
maxRight[i] = Math.max(maxRight[i + 1], heights[i + 1]);
}
// 计算可以存储的水量
for (int i = 1; i < n - 1; i++) {
int minHeight = Math.min(maxLeft[i], maxRight[i]);
if (minHeight > heights[i]) {
totalWater += minHeight - heights[i];
}
}
return totalWater;
}