[LeetCode]42. Trapping Rain Water java

/**42. Trapping Rain Water * @param height * @return 可接水最大量 */ public int trap(int[] A) { if (A == null || A.length == 0) return 0; int i, max, total = 0; int left[] = new int[A.length]; int right[] = new int[A.length]; // from left to right left[0] = A[0]; max = A[0]; for (i = 1; i < A.length; i++) { left[i] = Math.max(max, A[i]); max = Math.max(max, A[i]); } // from right to left right[A.length-1] = A[A.length-1]; max = A[A.length-1]; for (i = A.length-2; i >= 0; i--) { right[i] = Math.max(max, A[i]); max = Math.max(max, A[i]); } // trapped water (when i==0, it cannot trapped any water) for (i = 1; i < A.length-1; i++) { int bit = Math.min(left[i], right[i]) - A[i]; if (bit > 0) total += bit; } return total; }

分析每个格子的盛水两，然后相加 每个格子盛水量取决了两边高度，而且是左右最高之中最短的板 需要两遍遍历，一个从左到右，找最高的左短板；一个从右到左，找最高的右短板。最后记录下盛水量的总值就是最终结果了