Trapping Rain Water 363
Question
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.
Example
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Challenge
O(n) time and O(1) memory
O(n) time and O(n) memory is also acceptable.
Solution
前后指针法,时间复杂度O(n),空间复杂度O(1)。
1) 前指针指向数组头,后指针指向数组尾。
2) 比较前后指针,从小的那个开始(记录此时最初指针的值smaller),
3) 向后或前移动指针,当遇到小于等于它的元素(index为i)时,新增加的面积为smaller-heights[i],当遇到大于它的元素时停止.重复2-3步骤,直到前后指针交叠。
此处要说明的是,在第2步移动的必须是较小值的指针,这就好比一根短木板和一根长木板,若以长木板为基准向短木板推进,水会漏出,反之则可以。
代码如下:
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
// write your code here
if(heights == null || heights.length == 0){
return 0;
}
int start = 0;
int end = heights.length - 1;
int area = 0;
while(start < end){
if(heights[start] < heights[end]){
int smaller = heights[start];
while(start < end && heights[start] <= smaller){
area += smaller - heights[start];
start++;
}
}else{
int smaller = heights[end];
while(start < end && heights[end] <= smaller){
area += smaller - heights[end];
end--;
}
}
}
return area;
}
}