42. Trapping Rain Water
Tags: ‘Array’, ‘Two Pointers’, ‘Stack’
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.
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!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
Solution
-
方法1：对于每个i， 当前位置能装的水为 $min(max_left, max_right) - current_height$ 所以每个i左右扫描一遍，$O(n^2) O(1)$
- 方法2： 1有重复搜索，用两个array做memo，分别存储i位置左侧和右侧最大值。只需要扫描两遍。$O(n) O(n)$
public int trap(int[] height) { int[] left = new int[height.length]; int[] right = new int[height.length]; // left to right swipe int currLeftMax = Integer.MIN_VALUE; for (int i = 0; i < height.length; i++) { if (height[i] > currLeftMax) currLeftMax = height[i]; left[i] = currLeftMax; } // right to left swipt int currRightMax = Integer.MIN_VALUE; for (int i = height.length - 1; i >= 0; i--) { if (height[i] > currRightMax) currRightMax = height[i]; right[i] = currRightMax; } int result = 0; for (int i = 0; i < height.length; i++) { if (Math.min(left[i], right[i]) > height[i]) { result += Math.min(left[i], right[i]) - height[i]; } } return result; } - 方法3: two pointer $O(n) O(1)$ 无法理解。。。下次再说