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.

Solution 1:  for height[i], the height with water will be the min of max left bin and max right bin. So we can first find the max bin in the array, then do the left, min of the two will be max left; same way do the right, min of the two will be max right.

 public class Solution {  
   public int trap(int[] height) {  
     int n=height.length;  
     if (n==0) return 0;  
     int max=-1, index=-1;  
     for (int i=0; i<n; i++) {  
       if (height[i]>max) {  
         max=height[i];  
         index=i;  
       }  
     }  
     int res=0;  
     max=0;  
     for (int i=0; i<index; i++) {  
       if (height[i]>max) max=height[i];  
       res+=max-height[i];  
     }  
     max=0;  
     for (int i=n-1; i>index; i--) {  
       if (height[i]>max) max=height[i];  
       res+=max-height[i];  
     }  
     return res;  
   }  
 }