Leetcode 42. Trapping Rain Water 算法

描述
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
思路

第一种是找水位，具体做法是对于每个点，往左往右分别找出最高值，然后计算取较小者，这就是水位高度。减去当前点的高度就是水的体积。

class Solution { public int trap(int[] height){ int ans = 0; for (int i = 1; i < height.length; i++){ int left = 0, right = 0; for(int j = i; j >= 0; j--) { left = Math.max(left, height[j]); } for(int j = i; j < height.length; j++){ right = Math.max(right, height[j]); } ans += Math.min(left, right) - height[i]; } return ans; } }

我们发现上面的算法，有着很多重复计算，只要把结果缓存一下，就可以变成O（N）

public int trap(int[] height){ if (height == null) return 0; int ans = 0; int size = height.length; int[] left = new int[size]; int[] right = new int[size]; left[0] = height[0]; for (int i = 1; i < size; i++){ left[i] = Math.max(height[i], left[i-1]); } right[size - 1] = height[size - 1]; for (int i = size - 2; i >= 0; i--){ right[i] = Math.max(height[i], right[i+1]); } for (int i = 1; i < size - 1; i++){ ans += Math.min(left[i], right[i]) - height[i]; } return ans; }

时间复杂度肯定是最优了，之后只能优化空间复杂度了。

public int trap(int[] height){ int left = 0; int right = height.length - 1; int leftMax = 0, rightMax = 0; int ans = 0; while (left < right){ if (height[left] < height[right]){ if (height[left] >= leftMax) leftMax = height[left]; else ans += leftMax - height[left]; left++; }else{ if (height[right] >= rightMax) rightMax = height[right]; else ans += rightMax - height[right]; right--; } } return ans; }

【Leetcode 42. Trapping Rain Water】