首页 > 试题广场 >

最大间隔

[编程题]最大间隔
  • 热度指数：12044 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个递增序列，a1 <a2 <...<an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少？

输入描述:
第一行，一个正整数n(1<=n<=100),序列长度;接下来n个小于1000的正整数，表示一个递增序列。


输出描述:
输出答案。
示例1

输入

5
1 2 3 7 8

输出

4
算法知识视频讲解
添加回答
Java
牛客196305255号头像 牛客196305255号
最开始考虑这个间隔值就是两个间隔的最大值是有问题的，虽然能够通过，但是解决不了如：2 6 8 10 13 15这种情况，这个测试用例也水了吧。 
 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int[] arr=new int[n];
            int max=0;
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
                if(i>0)
                    max=Math.max(max,arr[i]-arr[i-1]);
            }
            int min=Integer.MAX_VALUE;
            for(int i=2;i<n;i++){
                min=Math.min(min,Math.max(arr[i]-arr[i-2],max));
            }
            System.out.println(min);
        }


发表于 2021-03-19 19:36:48 回复(0)
Java
soul_头像 soul_
分为n=3 n=4 n>=5三种情况讨论
package cn.greedy;package cn.greedy;

import java.util.Arrays;
import java.util.Scanner;

public class MinMaxGap {

    public static void read(){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext())
        {
            int n = scanner.nextInt();
            int []a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = scanner.nextInt();
            }
            int result = work(n,a);
            System.out.println(result);
        }
    }
    
    public static int work(int n,int []a){
        
        int []b = new int[n];
        
        if (n == 3) {
            return a[2] - a[0];
        }
        
        if (n == 4) {
            for (int j = 1; j < b.length; j++) {
                b[j] = a[j] - a[j-1];
            }
            if (b[2] >= b[1] && b[2] >= b[3]) {
                return b[3] > b[1] ? (b[1]+b[2]):(b[2]+b[3]);
            }else{
                int p = b[2] + b[1];
                int q = b[3] + b[2];
                return Math.min(Math.max(b[3], p), Math.max(b[1], q));
            }
            
            
            
        }
        
        
        if (n >= 5) {
            for (int j = 1; j < b.length; j++) {
                b[j] = a[j] - a[j-1];
            }
            Arrays.sort(b);
            return b[n-1];
        }
        
        return 0;
        
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
read();
    }

}

}


编辑于 2018-04-24 17:23:12 回复(0)
Java
qianhuan头像 qianhuan 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            int maxSpace = 0;
            for (int i = 1; i < arr.length; i++) {
                maxSpace = Math.max(maxSpace,arr[i] - arr[i-1]);
            }
            int tempMinMaxSpace = Integer.MAX_VALUE;
            for (int i = 2; i < arr.length; i++) {
                int tempSpace = arr[i] - arr[i-2];
                if(tempSpace <= maxSpace) {//如果去除当前数前后之间间隔（tempSpace）小于没有取除数的最大间隔（maxSpace） 去除后最大间隔的最小值 就是没有去处数的最大间隔
                    tempMinMaxSpace = maxSpace;
                    break;
                }else{//如果去除当前数前后之间间隔（tempSpace）大于没有取除数的最大间隔（maxSpace），这个值就是去除当前数最大间隔  
                    //好吧这个注释把我自己都绕进去了。。。
                    tempMinMaxSpace = Math.min(tempMinMaxSpace,tempSpace);
                }
            }
            System.out.println(tempMinMaxSpace);
        }
    }
}

发表于 2017-12-12 16:22:25 回复(0)
Java
ltt不在服务区了。。头像 ltt不在服务区了。。 
//最大间隔的最小值实际就是原来数组相邻元素间隔的最大值
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] num = new int[n];
            int[] d1 = new int[n - 1];
            for(int i = 0; i < n; i++){
                num[i] = sc.nextInt();
            }
            for(int i = 1; i < n; i++){
            	d1[i - 1] = num[i] - num[i - 1]; 
            }
            Arrays.sort(d1);
            System.out.println(d1[n - 2]);
        }
    }
}
编辑于 2017-09-08 22:43:22 回复(8)
Java
Thare头像 Thare

输入的时候记录所有的差值并保存在list中，同时记录最大的差值和下标。
遍历完后取最大差值及其分别与其左右差值的和的最小值

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            if (n <= 2) {
                System.out.println(0);
                continue;
            }
            List<Integer> list = new ArrayList<>();
            int i, gap, current;
            int index = -1, max = -1;
            int last = scanner.nextInt();
            for (i = 1; i < n; ++i) {
                current = scanner.nextInt();
                gap = last - current;
                last = current;
                if (Math.abs(gap) > max) {
                    max = Math.abs(gap);
                    index = i - 1;
                }
                list.add(gap);
            }
            if (index > 0) {
                max = Math.min(max, Math.abs(list.get(index) + list.get(index - 1)));
            }
            if (index < list.size() - 1) {
                max = Math.min(max, Math.abs(list.get(index) + list.get(index + 1)));
            }
            System.out.println(max);
        }
    }

}
发表于 2017-08-25 23:17:50 回复(0)
Java
命中全靠运气头像 命中全靠运气

import java.util.Scanner;


publicclass Main {


publicstaticvoid main ( String [] args ) {

Scanner sc = new Scanner (System. in ) ;

while ( sc .hasNext()){

int n = sc. nextInt () ;

int [] arr = new int [n] ;

for(int i=0;i<n;i++){

arr[i] =sc. nextInt () ;

}

if ( n < 3 ) {System. out . println ( 0 ) ;System. exit ( 0 ) ; }

for(int i=n-1;i>0;i--){

arr[i] = arr[i] -arr[i- 1 ] ;

}

int min = Integer .MAX_VALUE;

int pos = 0 ;

for(int i=1;i<n-1;i++){

int num = arr[i] +arr[i+ 1 ] ;

if (num<min){

min=num;

pos = i;

}

}

arr[pos+ 1 ] +=arr[pos] ;

arr[pos] = 0 ;

int max = Integer .MIN_VALUE;

for(int i=1;i<n;i++){

if (arr[i] >max) max=arr[i] ;

}

System .out. println (max) ;

}

}


}


发表于 2017-07-13 01:04:34 回复(0)
Java
.zZZ~~头像 .zZZ~~ 
import java.util.Scanner;

public class test2_5 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] num = new int[n];
			int maxChaZhi = 0;
			for (int i = 0; i < n; i++) {
				num[i] = scanner.nextInt();
				if (i >= 1) {
					int temp = num[i] - num[i - 1];
					if (temp > maxChaZhi) {
						maxChaZhi = temp;// 原始最大差值
					}
				}
			}
			int removeChaZhi = Integer.MAX_VALUE;
			for (int i = 1; i < n - 2; i++) {
				// 如果删除了 i 得到的最大差值最小值
				int temp_i = num[i + 1] - num[i - 1];
				if (temp_i < removeChaZhi) {
					removeChaZhi = temp_i; // 记录删除后的最小值
				}
			}
			int result = 0;
			if (removeChaZhi > maxChaZhi) {
				result = removeChaZhi; // 说明删除后的最小值比原始值大
			} else {
				result = maxChaZhi; // 否则就删除那个点，保留原始差值
			}
			System.out.println(result);
		}
	}
}


发表于 2017-04-19 15:29:34 回复(0)
Java
java的神秘男友script头像 java的神秘男友script 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int n=in.nextInt();
            int[] arr=new int[n];
            int[] brr=new int[n-1];
            int [] crr=new int[n-2];
            int max=0;
            boolean flag=false;
            for(int i=0;i<n;i++){
                arr[i]=in.nextInt();
            }
            for(int j=0;j<n-1;j++)
              {
                brr[j]=arr[j+1]-arr[j];
                  if(max<brr[j])
                     max=brr[j];
              }
            for(int y=0;y<n-2;y++){
                crr[y]=brr[y]+brr[y+1];
                if(crr[y]<max)
                    flag=true;
            }
            if(flag)
               System.out.println(max);
            else if(!flag)
               System.out.println(crr[0]);
        }
    }
}

发表于 2017-03-08 23:22:59 回复(1)
Java
王小叶头像 王小叶 
链接：https://www.nowcoder.com/questionTerminal/3a571cdc72264d76820396770a151f90
来源：牛客网


	//思路：         1 2 3 7 8





	//间隔：         1 1 4 1    d=4





	//删除后间隔 删2: 2 4 1      d=4





	//          删3: 1 5 1      d=5





	//          删7: 1 1 5      d=5





	//特点：删除后间隔在变大，最大间隔只能>=原间隔，且被改变的那个间隔为之前的两个之和





	importjava.util.*;





	publicclassJianGe {





	  publicstaticvoidmain(String[] args){





	      Scanner sc =newScanner(System.in);





	      while(sc.hasNext()){





	        intn=sc.nextInt();





	          /*String[] s=sc.nextLine().split(" ");





	          * int[] num=new int[s.length];





	          * for(int i=0;i<num.length;i++){





	          *     num[i]=Integer.parseInt(s[i]);





	          * }





	          * 由于数字可能不止一行，所以第一个这样做失败





	          */





	          //以上存储数据完毕





	          intd=Integer.MIN_VALUE;





	          int[] num=newint[n];





	            for(inti=0;i<n && sc.hasNext();i++){





	              num[i]=sc.nextInt();





	          }





	          //原始的最大间隔





	          int[] dOld=newint[num.length-1];





	          for(inti=0;i<num.length-1;i++){





	              dOld[i]=num[i+1]-num[i];





	              d=Math.max(d,dOld[i]);





	          }





	          //System.out.println(d);





	          //删除每个数字后，剩下的最大间隔





	          int[] dNew=newint[dOld.length-1];





	          intdMin=Integer.MAX_VALUE;





	          intdTemp=d;





	          for(inti=0;i<dNew.length;i++){





	              dTemp=Math.max(d,dOld[i]+dOld[i+1]); //dTemp是删除一个后的最大间隔





	              //注意：之前的错误写法：dTemp=Math.max(dTemp,dOld[i]+dOld[i+1]);导致每次和变量d比较





	              dMin=Math.min(dMin,dTemp);               //取出最小的最大间隔





	          }





	          System.out.println(dMin);





	      }





	  }





	}

发表于 2017-02-28 12:26:35 回复(0)
Java
錫氾華头像 錫氾華 
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[] a;
		while(in.hasNext()){
			int n = in.nextInt();
			a = new int[n];
			for(int i=0; i<n;i++){
				a[i] = in.nextInt();
			}			
			int maxDisMin = findMin(n, a);
            System.out.println(maxDisMin);
		}
	}
	
	public static int findMin(int n, int[] a){
		//初始化最大间隔
        int maxDis = 0;
        //初始化最大间隔最小值
		int maxDisMin = a[n-1] - a[0];
		//找出此序列未删除任何元素之前的最大间隔
		for(int j=0; j<n-1; j++){
			if(a[j+1] - a[j] > maxDis){
				maxDis = a[j+1] - a[j];
			}
		}
        //遍历删除元素a[i]（1<=i<=n-2）
		for(int i=1; i<n-1; i++){
            //初始化删除后最大间隔maxDisDel为未删除的最大间隔maxDis
			int maxDisDel = maxDis;
			if(a[i+1] - a[i-1] > maxDis){
                //如果a[i]前后两元素之差大于maxDis,更新maxDisDel
				 maxDisDel = a[i+1] - a[i-1];
			}
			if(maxDisDel < maxDisMin){
                //如果最大间隔小于maxDisMin，更新maxDisMin
				maxDisMin = maxDisDel;
			}
		}   	
		return maxDisMin;		
	}
}

发表于 2016-09-23 00:57:39 回复(0)
Java
詆調壹點头像 詆調壹點 
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			List<Integer> list = new LinkedList<Integer>();
			for (int i = 0; i < n; i ++ )
				list.add(sc.nextInt());
			int[] mark = new int[n - 2];
			for (int i = 0; i < mark.length; i ++ ) {
				List<Integer> temp = new LinkedList<>(list);
				temp.remove(i + 1);
				mark[i] = fun(temp);
			}
			Arrays.sort(mark);
			System.out.println(mark[0]);
		}
	}
	public static int fun(List<Integer> list) {
		int max = 0;
		for (int i = 1; i < list.size(); i ++ ) {
			int temp = list.get(i) - list.get(i - 1);
			max = max > temp ? max : temp;
		}
		return max;
	}
}

发表于 2016-08-31 16:09:09 回复(0)
Java
ztxuri头像 ztxuri
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = 0;
int[] numbers = null;
int result=Integer.MAX_VALUE,temp;
while(in.hasNextInt()){
n=in.nextInt();
numbers=new int[n];
for(int i=0;i<n;i++){
numbers[i]=in.nextInt();
}
for(int i=1;i<n-1;i++){
temp=getMaxGap(numbers,i);
if(temp<result)
result=temp;
}
System.out.println(result);
            
            result=Integer.MAX_VALUE;
}
}
public static int getMaxGap(int[] numbers,int m){
int result=0,temp;
for(int i=1;i<numbers.length;i++){
if(i==m){
temp=numbers[m+1]-numbers[i-1];
}else{
temp=numbers[i]-numbers[i-1];
}
if(temp>result){
result=temp;
}
}
return result;
}
}
从a(2)到a(n-1)计算最大间隔，取最小值。每次计算最大间隔时，当刚好到达删除的数，用下一个数减去前一个数。因为是递增的，下一个数减去当前数肯定小于下一个数减去前一个数。

发表于 2016-08-18 22:51:22 回复(0)
提交观点

问题信息

贪心 C++工程师 2016 蘑菇街 Java工程师
来自：美丽联合2016研发工...
难度：
14条回答 22836浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号