一个算法题目，

题目很简单，就是在在山峰，之间找出，可以填物的空间

package shu;

import java.util.ArrayList ;
import java.util.List ;

import org.junit.Test ;

public class Twitter {

	@Test
	public void twitterTest(){
		twitter(new int[]{9,7,8,6,7,5,6,4,5});
		twitter(new int[]{5,4,6,5,7,6,8,7,9});
		twitter(new int[]{10,8,12,10,14,12,16,14,18});
		twitter(new int[]{2,5,1,2,3,4,7,7,6});
		twitter(new int[]{2,5,1,3,1,2,1,7,7,6});
		twitter(new int[]{6,1,4,6,7,5,1,6,4});
		twitter(new int[]{9,6,1,2,3,4,50,1,9});
	}
	
	public void twitter(int[] in){
		int inLeng = in.length-1;
		if( inLeng < 2){
			System.out.println("墙少于3个，不无组成凹点") ;
			return;
		}
		// i 是循环数， inOne ，inTwo ，inTree 一次取三个才能拿比较出一个高峰
		//listSize 高峰多少   subscript定位 高峰的下标， mainPeak 最高峰巅峰的高度，mainSub 最高峰的下标
		int i = 2 , inOne = in[0],inTwo = in[1] , inThree = in[2] ,listSize ,subscript=1, mainPeak = 0 , mainSub = -1;
		List<TwitterClass> list = new ArrayList<>(inLeng - inLeng/3);//原数组的三分之二大小。因为怕遇到2121212这样的蛋疼的
		TwitterClass twOne,twTwo = null;
		if(inOne > inTwo){//如果第一个墙比第二个墙高，那么这个就是峰
			twOne = new TwitterClass(0, inOne);
			mainPeak = inOne;
			mainSub = 1;
			inOne = inTwo;
			inTwo = inThree;
			subscript = 2;
			inThree = in[++i];
			list.add(twOne);
		}
		if(in[inLeng] > in[inLeng-1]){//如果最后一个墙比最后第二个墙高，那么这个就是峰，因为是最后一个不需要进行标记等
			twTwo = new TwitterClass(inLeng, in[inLeng]);
		}
		inLeng = inLeng -1;
		for( ; ;){
			if(inOne < inTwo && inTwo >= inThree ){
					if(inThree == inTwo){						
						subscript++;
					}
					twOne = new TwitterClass(subscript, inTwo);
					list.add(twOne);
					if(mainPeak < inTwo){
						mainPeak = inTwo;
						mainSub =  list.size();
					}
			}
			if(i == inLeng){
				if(inTwo < inThree){//最后2 3个，不需要在次循环验证。这里处理
					if(twTwo == null){//如果有twTwo 那么最后二个不是高峰
						twTwo = new TwitterClass(i, inThree);
					}
				}
				if(twTwo!=null){//这里把最后一个峰加入，同时，确定是不是巅峰						
					list.add(twTwo);
					if(mainPeak < twTwo.getValues()){
						mainPeak = twTwo.getValues();
						mainSub  = list.size();
					}
				}
				break;
			}
			inOne = inTwo;
			inTwo = inThree;
			subscript++;
			inThree = in[++i];
		}
		//System.out.println(list.toString()) ;
		listSize = list.size();
		if( listSize <2){
			System.out.println("高峰小于两个，不存在凹点") ;
			return;
		}
		List<TwitterClass> listTwo;
		boolean bx =false ; 
		if(listSize > 2){//这里是排除两做高峰的中的低峰 比如 7 3 2 2 7 ，3 2 2是低峰。需要排除
			List<TwitterClass> listThree = null;
			boolean b = true;//用区别，峰的规则，fasle是递增和递减。true就是中峰
			if( mainSub == 1){//最后高峰是第一个，那么高峰高度是递减，所以，需要从最后个高峰（也就是最低的高峰）开始计算，里面的参数是初始化循环需要的参数
				i = listSize-1;
				listSize = 0;
				mainPeak = -1;
				b = false;
				bx =true;
			}else{
				mainPeak = 1;
				i = 0;
				if( mainSub == listSize){//最后
					b = false;
				}
				listSize = listSize- 1;
			}
			listTwo = new ArrayList<>(list.size());
			twOne = list.get( i );
			listTwo.add(twOne);
			for( ; ; ){
				i=i+ mainPeak;
				if(b){
					if( i == mainSub){//当遇到，中峰的巅峰，需要使用递减的规则进行计算
						listTwo.add(list.get(mainSub-1));
						i = listSize;
						listSize = mainSub;
						mainPeak = -1;
						listThree = listTwo;
						listTwo = new ArrayList<>(list.size());
						listTwo.add(list.get(list.size()-1));
						b = false;
						//bx = true;
					}
				}else{//这里是排除低峰
					twTwo = list.get( i );
					if(twOne.getValues() < twTwo.getValues()){
						listTwo.add(twTwo);
					}
				}
				if( i == listSize)
					break;
				twOne = twTwo;
			}
			if(listThree != null){//因为中峰使用同时使用了递增和递减，所有需要整合下
				listThree.addAll(listTwo);
				listTwo = listThree;
				//bx = false;
			}
		}else{
			listTwo = list;
		}
		list = null;
		//System.out.println(listTwo.toString()) ;
		
		i =0;
		twOne = listTwo.get(i++);
		listSize = listTwo.size();
		inThree = 0;
		
		int start = twOne.getSubscript(), end , zhong = 1, daShu =0, inValue = 0;
		if(bx){
			zhong = -1;
		}
		inOne = twOne.getValues();
		start = start +zhong;
		for( ; ;){
			twTwo = listTwo.get(i++);
			inTwo =twTwo.getValues();
			end = twTwo.getSubscript();
			if(inOne > inTwo){
				subscript = inTwo ;
				daShu = inOne;
			}else{
				subscript = inOne;
				daShu = inTwo;
			}
			
			for( ; ;){
				inValue = in[start];
				if( inValue < daShu){
					inThree = inThree + subscript - inValue;
				}
				start = start +zhong;
				if(start == end )
					break;
			}
			if( i == listSize)
				break;
			start = end + zhong;
			inOne = inTwo;
		}
		System.out.println(inThree) ;
	}
	
	static final class TwitterClass{
		private int subscript;
		private int values;
		
		public TwitterClass(int subscript , int values){
			this.subscript = subscript;
			this.values = values;
		}
		
		public int getSubscript() {
                        	return subscript ;
                        }
		public void setSubscript(int subscript) {
                        	this.subscript = subscript ;
                        }
		public int getValues() {
                        	return values ;
                        }
		public void setValues(int values) {
                        	this.values = values ;
                        }
		public String toString(){
			StringBuilder sb = new StringBuilder();
			sb.append("subscript = ");
			sb.append(this.subscript);
			sb.append("  values = ");
			sb.append(this.values);
			sb.append("\n");
			return sb.toString();
		}
	}
	
}
/*
 * for( ; ;){
		if(inOne <= inTwo){
			if(inTwo >= inThree ){
				if(inThree == inTwo){
					subscript++;
				}
				twOne = new TwitterClass(subscript, inTwo);
				list.add(twOne);
			}else{
				if(i == inLeng){
					break;
				}else if(i == inLeng -1){
					if(twTwo != null){
						
					}
				}
			}
		}else{
			if(i == inLeng){
				break;
			}
			inOne = inTwo;
			inTwo = inThree;
			subscript++;
			inThree = in[++i];
		}
	}
	*/

 空间。