[leetcode] Trapping Rain Water

首先，碰到这样的题目不要慌张，挨个分析每个A[i]能trapped water的容量，然后将所有的A[i]的trapped water容量相加即可 其次，对于每个A[i]能trapped water的容量，取决于A[i]左右两边的高度（可延展）较小值与A[i]的差值，即volume[i] = [min(left[i], right[i]) - A[i]] * 1，这里的1是宽度，如果the width of each bar is 2,那就要乘以2了” 那么如何求A[i]的左右高度呢？ 要知道，能盛多少水主要看短板。那么对每个A[i]来说，要求一个最高的左短板，再求一个最高的右短板，这两个直接最短的板子减去A[i]原有的值就是能成多少水了。 所以需要两遍遍历，一个从左到右，找最高的左短板；一个从右到左，找最高的右短板。最后记录下盛水量的总值就是最终结果了。 有人可以用O(1)space 做 大概思路是看左右bottom neck, 要学习

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution { public int trap(int[] height) { if (height == null || height.length <= 2) return 0; int leftHighest[] = new int[height.length]; int rightHighest[] = new int[height.length]; leftHighest[0] = height[0]; rightHighest[height.length-1] = height[height.length-1]; for (int i = 1, j = height.length-2; i < height.length; i++, j--){ leftHighest[i] = Math.max(leftHighest[i-1], height[i]); rightHighest[j] = Math.max(rightHighest[j+1], height[j]); } int sum = 0; for (int i = 1; i < height.length-1; i++){ int area = Math.min(leftHighest[i], rightHighest[i])-height[i]; area = area < 0?0:area; sum += area; } return sum; } }