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;}