leetcode 42 接雨水
思路
刚开始一点思路也没有
下面这个讲的非常好
https://zhuanlan.zhihu.com/p/125074613
dp的思路
就是找这个点左边最大值和右边最大值
代码
public int trap(int[] height) {
int[] leftMax = new int[height.length];
int[] rightMax = new int[height.length];
leftMax[0] = height[0];
for (int i = 1; i < height.length; i++) {
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
rightMax[height.length-1] = height[height.length-1];
for (int i = height.length - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i+1],height[i]);
}
int result = 0;
for (int i = height.length - 2; i > 0; i--) {
result = result + Math.min(leftMax[i], rightMax[i])-height[i];
}
return result;
}