11. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
public class Solution { public int maxArea(int[] height) { int leftInd = 0; int rightInd = height.length-1; int leftMax = 0; int rightMax = 0; int areaAax = 0; while(leftInd
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. 
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!
public class Solution { public int trap(int[] height) { if(height.length == 0) return 0; //Create a "skyline" such that //1.the left part of this skyline is based on the max value ever seen to the left //2.the right part of this skyline is based on the max value ever seen to the right //3. two parts merge at the maximum point. int[] leftBasedMax = new int[height.length]; leftBasedMax[0] = height[0]; int maxIndex = 0; for(int i = 1; i height[maxIndex]) { leftBasedMax[i] = height[i]; maxIndex = i; } else leftBasedMax[i] = leftBasedMax[i-1]; } //Improve: you can save an array space, if you do an extra iteration first to find the max value index. int[] rightBasedMax = new int[height.length]; rightBasedMax[height.length-1] = height[height.length-1]; for(int i = height.length-2; i>maxIndex; --i) { rightBasedMax[i]=Math.max(rightBasedMax[i+1],height[i]); } int sum = 0; for(int i = 0; i<=maxIndex; ++i) sum+=leftBasedMax[i]-height[i]; for(int i = maxIndex+1; i
More improvements: Use two pointers, the left pointer go right-ward, and the right pointer go left-ward.
public class Solution { public int trap(int[] height) { if(height.length == 0) return 0; int left = 0; int right = height.length - 1; int sum = 0; int leftMax = height[left]; int rightMax = height[right]; while (left < right) { //The water can be guaranteed to hold at least by two ends //Just move the shorter end index inward. if (leftMax < rightMax) { sum += leftMax - height[left]; ++left; leftMax = Math.max(leftMax, height[left]); } else { sum += rightMax - height[right]; --right; rightMax = Math.max(rightMax, height[right]); } } return sum; }}