leetcode hard模式专杀之42. Trapping Rain Water

继续刷leetcode hard模式， 这题是我喜欢的类型，可能因为我空间想象力还行，这题在2次内通过oj，

思路如下： 可以这样想， 每个数字上方拖着的空间如果左边有墙，右边也有墙，那么这个水就流不出去，而墙可以用左边最高的数字和右边最高的数字来表示，例如位置i,左边最高墙是3，右边最高墙是4， 那么i上能托几格水呢？当然是min(3,4)-i啦，所以这个问题就转换为如何高效率地找出每个位置i的左边最高墙和右边最高墙来，

用两个hashmap来做就好了，这样时间复杂度可以控制在O（n）

思路就这么简单， 代码如下：

public class Solution { public int trap(int[] height) { int globalMax = 0; for(int k = 0; k<height.length; k++){ globalMax = Math.max(globalMax, height[k]); } // key is Map<Integer, Integer> leftMaxMap = new HashMap(); Map<Integer, Integer> rightMaxMap = new HashMap(); for(int i = 0; i<height.length; i++){ if(i==0){ leftMaxMap.put(i, 0); }else{ leftMaxMap.put(i, Math.max(leftMaxMap.get(i-1), height[i-1])); } } for(int j = height.length-1;j>=0;j--){ if(j==height.length-1){ rightMaxMap.put(j, 0); }else{ rightMaxMap.put(j, Math.max(rightMaxMap.get(j+1), height[j+1])); } } int face = 0; for(int m=0; m<height.length; m++){ int tmp = (Math.min(leftMaxMap.get(m), rightMaxMap.get(m))-height[m]); face+=tmp<=0?0:tmp; } return face; } }