题目
重点题目，深刻理解！！！
解法1：备忘录
O(N) + O(N)
class Solution {
public int trap(int[] height) {
int n = height.length, res = 0;
int[] lMax = new int[n];
int[] rMax = new int[n];
lMax[0] = height[0];
rMax[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
lMax[i] = Math.max(lMax[i - 1], height[i]);
}
for (int i = n - 2; i >=0; --i) {
rMax[i] = Math.max(rMax[i + 1], height[i]);
}
for (int i = 0; i < n; ++i) {
res += Math.min(lMax[i], rMax[i]) - height[i];
}
return res;
}
}
解法2：双指针
O(N) + O(1)
class Solution {
public int trap(int[] height) {
int n = height.length;
int left = 0, right = n - 1, res = 0, lMax = height[0], rMax = height[n - 1];
while (left <= right) {
lMax = Math.max(lMax, height[left]);
rMax = Math.max(rMax, height[right]);
if (lMax <= rMax) {
res += lMax - height[left];
++left;
} else {
res += rMax - height[right];
--right;
}
}
return res;
}
}
