首页 > 代码库 > Leetcode-Trapping Rain Water
Leetcode-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!
Analysis:
We scan the whole array twice. First: from head to end; Second: from end to start.
In every scan, we record the current bar for rain trapping. If the value of current column is less than the bar, then current store += bar-currentValueOfColumn; Else, current store is end, we then add the current store into the total store, and reset the bar as currentValueOfColumn.
Solution:
1 public class Solution { 2 public int trap(int[] A) { 3 if (A.length==0) return 0; 4 if (A.length==1) return 0; 5 int index = 1; 6 int bar = A[0]; 7 int total = 0; 8 int curStore = 0; 9 boolean[] count = new boolean[A.length];10 11 //We need to record which column has been counted during the first scan. 12 for (int i=0;i<count.length;i++) count[i] = false;13 List<Integer> countList = new ArrayList<Integer>();14 15 while (index<A.length){16 int curBar = A[index];17 if (curBar<bar){18 curStore+= (bar-curBar);19 countList.add(index);20 } else {21 total += curStore;22 curStore = 0;23 bar = curBar;24 for (int i=0;i<countList.size();i++) count[countList.get(i)]=true;25 countList.clear();26 }27 index++;28 }29 30 bar = A[A.length-1];31 index = A.length-2;32 curStore = 0;33 while (index>=0){34 int curBar = A[index];35 if (curBar<bar && !count[index])36 curStore+= (bar-curBar);37 else if (curBar>bar){38 total += curStore;39 curStore = 0;40 bar = curBar;41 } 42 index--;43 }44 45 46 return total; 47 }48 }
NOTE: We need to record which column has been counted in the first scan, we then ignor these column in the second scan.
Leetcode-Trapping Rain Water