题目
题目链接
题解
第一阶段:暴搜
class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < height.length; i++) {
int left = 0, right = 0;
for (int l = i - 1; l >= 0; l--) {
if (height[l] > left) {
left = height[l];
}
}
for (int r = i + 1; r < height.length; r++) {
if (height[r] > right) {
right = height[r];
}
}
res += calculateWaterLevel(left, right, height[i]);
}
return res;
}
private int calculateWaterLevel(int left, int right, int myself) {
int res = Math.min(left, right) - myself;
return res < 0 ? 0 : res;
}
}
第二阶段:动态规划
class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int res = 0;
int[] left = new int[height.length];
int[] right = new int[height.length];
int t = 0;
for (int i = 0; i < height.length; i++) {
if (height[i] > t) {
left[i] = height[i];
t = height[i];
} else {
left[i] = t;
}
}
t = 0;
for (int i = right.length - 1; i >= 0; i--) {
if (height[i] > t) {
right[i] = height[i];
t = right[i];
} else {
right[i] = t;
}
}
for (int i = 0; i < height.length; i++) {
res += calculateWaterLevel(left[i], right[i], height[i]);
}
return res;
}
private int calculateWaterLevel(int left, int right, int myself) {
int res = Math.min(left, right) - myself;
return res < 0 ? 0 : res;
}
}
第三阶段:双指针
class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
// res结果
// left左指针左边最大值
// right右指针右侧最大值
// lp, rp左右指针
int res = 0, left = 0, right = 0, lp = 0, rp = height.length - 1;
while (lp < rp) {
if (height[lp] < height[rp]) {
// 左指针右移
left = Math.max(left, height[lp]);
if (height[lp] < left) {
res += (left - height[lp]);
}
lp++;
} else {
// 右指针左移
right = Math.max(right, height[rp]);
if (height[rp] < right) {
res += (right - height[rp]);
}
rp--;
}
}
return res;
}
}