接雨水
题目描述：
给定 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
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
思路分析：
作为力扣的经典hard题和面经的常考题，本题的的解法也是非常多样。下面列举几种常见解法：
解法一：按行求
整个思路就是，求第 i 层的水，遍历每个位置，如果当前的高度小于 i，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加 111。
如果求高度为 i 的水，首先用一个变量 temp 保存当前累积的水，初始化为 000。从左到右遍历墙的高度，遇到高度大于等于 i 的时候，开始更新 temp。更新原则是遇到高度小于 i 的就把 temp 加 111，遇到高度大于等于 i 的，就把 temp 加到最终的答案 ans 里，并且 temp 置零，然后继续循环。
但这个解法现在 AC 不了了，会报超时，也就不展示代码了
解法二：按列求
求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。至于装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。
所以，根据较矮的那个墙和当前列的墙的高度可以分为两种情况。
- 较矮的墙的高度大于当前列的墙的高度
- 较矮的墙的高度小于等于当前列的墙的高度
只有当较矮的墙的高度大于当前列的墙的高度时才能存水，存水量为矮的墙的高度减去当前列的墙的高度。
代码展示：
class Solution {
public int trap(int[] height) {
int sum = 0;
//最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
for (int i = 1; i < height.length - 1; i++) {
int max_left = 0;
//找出左边最高
for (int j = i - 1; j >= 0; j--) {
if (height[j] > max_left) {
max_left = height[j];
}
}
int max_right = 0;
//找出右边最高
for (int j = i + 1; j < height.length; j++) {
if (height[j] > max_right) {
max_right = height[j];
}
}
//找出两端较小的
int min = Math.min(max_left, max_right);
//只有较小的一段大于当前列的高度才会有水，其他情况不会有水
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
}解法三: 动态规划
在解法二中，对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。用两个数组记录当前每个列的左右最大值，避免重复遍历。
class Solution {
public int trap(int[] height) {
int sum = 0;
//用来存放当前的左端最大值
int[] max_left = new int[height.length];
//用来存放当前的右端最大值
int[] max_right = new int[height.length];
//如果即将存入的的高度大于当前左端最大值，则替换最大值
for (int i = 1; i < height.length - 1; i++) {
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
}
//如果即将存入的的高度大于当前右端最大值，则替换最大值
for (int i = height.length - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
//找出两端较小的，只有较小的一段大于当前列的高度才会有水，其他情况不会有水
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
}
解法四：双指针
动态规划中，我们常常可以对空间复杂度进行进一步的优化。例如这道题中，可以看到，max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次，然后就再也不会用到了。所以我们可以不用数组，只用两个指针就行了。
首先比较当前列左右两墙的高度大小，将那个较小的与当前列进行比较
class Solution {
public int trap(int[] height) {
int sum = 0,maxleft = 0,maxright = 0;
//左指针加进去
int left = 1;
// 加右指针进去
int right = height.length - 2;
for (int i = 1; i < height.length - 1; i++) {
//如果左指针的前一个值小于右指针的后一个值
if (height[left - 1] < height[right + 1]) {
//那么从左到右更，记录当前左端最大值
maxleft = Math.max(maxleft, height[left - 1]);
//如果当前左指针指向的高度小于左墙，则两者的高度差即为存水量
if (maxleft > height[left]) {
sum = sum + (maxleft - height[left]);
}
left++;
}
//否则从右到左更，记录当前右端最大值
else {
maxright = Math.max(maxright, height[right + 1]);
//如果当前右指针指向的高度小于右墙，则两者的高度差即为存水量
if (maxright > height[right]) {
sum = sum + (maxright - height[right]);
}
right--;
}
}
return sum;
}
}
