题目很简单，就是在在山峰，之间找出，可以填物的空间
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];
}
}
*/
空间。