import java.util.Stack; public class TrappingRainWater { public int trap(int[] height) { int left = 0; int right = height.length - 1; int res = 0; int leftMax = 0; int rightMax = 0; while (left < right) { if (height[left] < height[right]) { leftMax = Math.max(height[left], leftMax); res += leftMax - height[left]; left++; } else { rightMax = Math.max(height[right], rightMax); res += rightMax - height[right]; right--; } } return res; } public int trap1(int[] A) { if (A==null) return 0; Stack s = new Stack(); int i = 0, maxWater = 0, maxBotWater = 0; while (i < A.length){ if (s.isEmpty() || A[i]<=A[s.peek()]){ s.push(i++); } else { int bot = s.pop(); maxBotWater = s.isEmpty()? // empty means no il 0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1); maxWater += maxBotWater; } } return maxWater; } public static void main(String[] args) { // TODO Auto-generated method stub int s[]= {0,1,0,2,1,0,1,3,2,1,2,1}; int num1[]= {2,1,0,3,0,0,4}; int n=new TrappingRainWater().trap1(num1); System.out.println(n); } }