目录
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
核心思路：对于每一个位置i，只需要知道该位置左右两侧最高的柱子高度，即可求出该位置能存储的水量。
一种非常巧妙的方法是：用left和right限定左右区间，maxLeft、maxRight记录遍历过程中遇到的最大值。
当height[left] <= height[right]时：
但注意！由于是左边界在向中间移动，所以左侧柱子的高度必定小于height[right]的高度！！！
而此时maxRight不一定大于height[right]（因为还没更新），所以较矮的一定是maxLeft，也就是说ans += (maxLeft - height[left])，而不是ans += (min(maxLeft, maxRight) - height[left])
class Solution {
public int trap(int[] height) {
if (height.length <= 2) return 0;
int left = 0, right = height.length - 1;// 标记左右边界
int maxLeft = 0, maxRight = 0;// 记录目前遇到的最大高度，初始化为0!!!
int ans = 0;
while (left < right) {
if (height[left] <= height[right]) {
if (height[left] > maxLeft) maxLeft = height[left];
else ans += (maxLeft - height[left]);// !!!到这里表示一定有右边界大于maxLeft，所以只需要取maxLeft即可，而不是取min(maxLeft, maxRight)，因为maxRight可能还没来得及更新
left++;
} else {
if (height[right] > maxRight) maxRight = height[right];
else ans += (maxRight - height[right]);// !!!同上
right--;
}
}
return ans;
}
}数组maxLeft和maxRight分别记录从左到右、从右到左遍历过程中当前位置遇到的最大值，其中maxLeft[i]表示，从左向右遍历到 i 时，遇到的最大值，maxRight同理。
再次遍历数组height，对每一个位置 i 计算ans += (Math.min(maxLeft[i], maxRight[i]) - height[i]);即对每一个位置 i 计算该位置可以存储的最大水量。
class Solution {
public int trap(int[] height) {
if (height.length <= 2) return 0;
int[] maxLeft = new int[height.length];// 存储从左到右中最高的柱子高度
int[] maxRight = new int[height.length];// 存储从右到左中最高的柱子高度
maxLeft[0] = height[0];
maxRight[height.length - 1] = height[height.length - 1];
for (int i = 1; i < height.length; i++) {
maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
}
for (int i = height.length - 2; i >= 0; i--) {
maxRight[i] = Math.max(maxRight[i + 1], height[i]);
}
int ans = 0;
for (int i = 1; i < height.length - 1; i++) {
ans += (Math.min(maxLeft[i], maxRight[i]) - height[i]);
}
return ans;
}
}
额外开两个数组，空间O(n)。
其实在遍历求解过程中，只需要知道当前位置左侧最高的柱子和右侧最高的柱子高度即可。
一种非常巧妙的方法是：用left和right限定左右区间，maxLeft、maxRight记录遍历过程中遇到的最大值。
当height[left] <= height[right]时：
但注意！由于是左边界在向中间移动，所以左侧柱子的高度必定小于height[right]的高度！！！
而此时maxRight不一定大于height[right]（因为还没更新），所以较矮的一定是maxLeft，也就是说ans += (maxLeft - height[left])，而不是ans += (min(maxLeft, maxRight) - height[left])