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!

这里计算面积不用一般几何书的方法，这里是两边往中间遍历，记录当前第二高点secHight，然后利用这个第二高点减去当前历经的柱子，剩下就装水容量了。

为什么是第二高点？因为两边比较，最高的点不用动，只移动第二高点。

第一个思路，按照上图的思想就能写出非常简洁的程序了，时间复杂度为O(n)：

int trap(int A[], int n) {
		int secHight = 0;
		int left = 0;
		int right = n-1;
		int area = 0;
		while (left < right){
			if (A[left] < A[right]){
				secHight = max(A[left], secHight);
				area += secHight-A[left];//计算当前格的能装雨水的容量
				left++;
			} else {
				secHight = max(A[right], secHight);
				area += secHight-A[right];
				right--;
			}
		}
		return area;
	}

题目二

public class Solution {
    public static void main(String[] args){
    	System.out.print(get_smallest("63534",2));
    }
    public static String get_smallest(String n, int k){
    	int len=n.length()-k;//最后的序列长
    	int index=0;
    	int temp=0;
    	String result="";//输出结果
    	for(int i=0;i<len;i++){
    		int min=9;
    		for(int j=index;j<=n.length()-len+i;j++){
    			if(Integer.parseInt(String.valueOf(n.charAt(j)))<min){
    				index=j+1;
    				min=Integer.parseInt(String.valueOf(n.charAt(j)));
    			}
               
    		}
    		result+=min+"";
    	}
    	return result;
    } 
}

题目三

public class Solution {
     public static void main(String[] args){
        	int[] list1={1,5,8,8,9};
        	int[] list2={2,7,7};
        	System.out.print(get_median(list1,list2));
     }
     public static int get_median(int[] list1,int[] list2){
    	 int len1=list1.length;
    	 int len2=list2.length;
    	 if(len1==0 && len2==0) return 0;
    	 if(len1==0) return list2[len2/2];
    	 if(len2==0) return list1[len1/2];
    	 int median=(len1+len2)/2-2;
    	 int index_1=0;
    	 int index_2=0;
    	 int result=Integer.MIN_VALUE;
    	 while(index_1+index_2<=median && index_1<len1 && index_2<len2){
    		 if(list1[index_1]<=list2[index_2]){
    			 result=list2[index_2];
    			 index_1++;
    		 }
    		 else{
    			 result=list1[index_1];
    			 index_2++;
    		 }    		            
    	 }
    	 if(index_1+index_2-1==median){
    		 return result;
    	 }
    	 else{
    		 if(index_1==len1){
    			return list2[median-len1];
    		 }
    		 else{
    			 return list1[median-len2];
    		 }
    	 }
    	    	 
    	 
     }  
}

/********************************

* 本文来自博客  “李博Garvin“

* 转载请标明出处:http://blog.csdn.net/buptgshengod

******************************************/