首页 > 试题广场 >

最大间隔

[编程题]最大间隔

热度指数：12022 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个递增序列，a₁ <a₂ <...<a_n 。定义这个序列的最大间隔为d=max{a_i+1 - a_i }(1≤i<n),现在要从a₂ ,a₃ ..a_n-1 中删除一个元素。问剩余序列的最大间隔最小是多少？

输入描述:

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

输出描述:

输出答案。

示例1

输入

5
1 2 3 7 8

输出

算法知识视频讲解

nailperry

解题思路：

1.先计算原始数组相邻间隔，并在计算的过程中记录最大相邻间隔maxFull。

2.删除ai(1≤i<n)后所得新数组的最大相邻间隔只会在a[i+1]-a[i-1]与maxFull中取值，也就是Math.max(arr[i+1]-arr[i-1], maxFull)。

3.记录每一次删除ai(1≤i<n)后所得最大相邻间隔的最小值。

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(),i;
			int arr[] = new int[n];
			for (i = 0; i < n; i++) {
				arr[i] = in.nextInt();
			}
			int maxFull = Integer.MIN_VALUE,minMaxGap = Integer.MAX_VALUE;
			for (i = 1; i < n; i++) {
				maxFull = Math.max(maxFull, arr[i]-arr[i-1]);
			}
			for (i = 1; i < n-1; i++) {
				minMaxGap = Math.min(minMaxGap, Math.max(arr[i+1]-arr[i-1], maxFull));
			}
			System.out.println(minMaxGap);
		}
		in.close();
	}
}

发表于 2015-09-22 11:34:40 回复(5)

卷积神经网络哦

第一思路就是O(n^2)的暴力试了一下居然能过
题目很人性化的设计了不能删掉第一个和最后一个，省去了不少麻烦的判断。
但是此题显然有更好的办法提供一个O(n)的解法
删去的数左右差会变成一个更大的差，和最大差比较一下即可然后在求这个比较后较大值的最小值

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e2 + 5;
int arr[maxn];
int main(){
    int n;
    while(scanf("%d", &n) == 1){
        memset(arr, 0, sizeof(arr));
        for(int i=0;i<n;i++) scanf("%d", &arr[i]);
        int max_a = 0, min_a = 1e5;
        for(int i=1; i<n; i++) max_a = max(max_a, arr[i]-arr[i-1]);
        for(int i=1; i<n-1; i++) {
            min_a = min(max(max_a, arr[i+1]-arr[i-1]), min_a);
        }
        printf("%d\n", min_a);
    }
    return 0;
}

发表于 2018-09-03 17:39:33 回复(0)

Java

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)

Python

华科平凡

python解法如下：
gaps是两个相临数之间的差的列表
delgaps是删除一个数后，相临两个数之间的差的列表。
如果gaps中最大数大于等于delgaps中最小的数，直接返回该数。
否则返回delgaps中最小的数。

while True:
    try:
        a,b=input(),list(map(int,input().split()))
        gaps,delGaps=[],[]
        for i in range(1,len(b)):
            gaps.append(b[i]-b[i-1])
        for i in range(1,len(gaps)):
            delGaps.append(gaps[i]+gaps[i-1])
        print(max(gaps) if max(gaps)>=min(delGaps) else min(delGaps))
    except:
        break

发表于 2017-09-16 09:57:25 回复(0)

Agalloch_Mind

分析：原序列是一个递增序列，设原序列的最大间隔值为max。那么大家想一下，你删除任何位置的数所获得的新序列的最大间隔值只会比max大，不会比max小。所以这个题其实就是在求原数列的最大间隔值。

import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n=in.nextInt();
			int[] a=new int[n];
			for(int i=0; i<n; i++)
				a[i]=in.nextInt();
			int max=0;
			for(int i=1; i<n;i++)
				max=Math.max(max, a[i]-a[i-1]);
			System.out.println(max);
		}
	}
}

发表于 2017-08-30 22:39:38 回复(2)

毛毛~

if 原来最大间隔出现在数组两边：

结果是第二大的最大间隔

else ：

结果就是原来那个最大的间隔

#include<iostream>
using namespace std;
int main(){
	int n;
	while (cin >> n){
		int index1 = 0;
		int a,b;
		cin >> a;
		int Max1 = -1;
		int Max2 = -1;
		for (int i = 0; i < n-1 ; ++i){
			cin >> b;
			int v = b - a;
			if (v > Max1){
				Max1 = v;
				index1 = i;
			}
			else if (v > Max2){
				Max2 = v;
			}
			a = b;
		}
		cout << ((index1 == 0 || index1 == n - 2) ? Max2 : Max1)<<endl;
	}
	return 0;
}

发表于 2017-03-19 18:41:24 回复(3)

南邮陈丹伟

//正常人写法，适合新手看
import java.util.Scanner;
public class Main {
    
    public static void main(String[] args) {
        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 max_d = Integer.MIN_VALUE;
        	for(int i=1;i<n;i++){
        		int d = a[i] - a[i-1];
        		if(d>max_d)
        			max_d = d;
        	}
        	int max_min_d = max_d;
        	boolean flag = false;
        	for(int i=2;i<n;i++){
        		int d = a[i]-a[i-2];
        		if(d<max_d)
        		{
        			flag= true;
        			break;
        		}
        		else if(max_min_d == 4 && d>max_min_d){
        			max_min_d = d;
        		}else if(d<max_min_d){
        			max_min_d = d;
        		}
        			
        	}
        	
        	if(flag)
        		System.out.println(max_d);
        	else
        		System.out.println(max_min_d);
        	
        }
        scanner.close();
    }
}

发表于 2017-02-11 10:17:22 回复(0)

JustYoung

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int[] array = new int[n];
			for (int i = 0; i < n; ++i) {
                array[i] = scan.nextInt();
            }
            int[] dis = new int[n - 1];
            int max = Integer.MIN_VALUE;
            for (int i = 1; i < n; ++i) {
                dis[i - 1] = array[i] - array[i - 1];
                max = Math.max(dis[i - 1], max);
            }
            int min = Integer.MAX_VALUE;
            for (int i = 1; i < dis.length; ++i) {
                int temp = Math.max(max, dis[i] + dis[i - 1]);
                min = Math.min(min, temp);
            }
            System.out.println(min);
        }
    }
}

发表于 2016-08-25 22:57:04 回复(0)

RunningLee

//遍历一次得到max。
//len为3，max需要更新，其他情况直接输出即可。
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> data;
	int n;
	while(cin>>n)
	{
		data.clear();
		int m;
	    for(int i=0;i<n;i++)
	    {
		   cin>>m;
		   data.push_back(m);
	    }
		int max=-1;
		int len=data.size();
	    for(int i=1;i<len;i++)
	    {
		    if((data[i]-data[i-1])>max)
		    {
			 max=data[i]-data[i-1];
		    }
	    }
		if(len==3)
		{
			return data[2]-data[0];
		}
		else
		{
			cout<<max<<endl;
		}
	}
	return 0;
}

发表于 2016-03-31 13:46:48 回复(0)

C/C++

~一念执着~

int main(){
    int n;
    while(cin>>n){
        int tmp1=0,tmp2=0,max=0;
        while(n--){
            cin>>tmp2;
            max=tmp1>0&&(tmp2-tmp1)>max?tmp2-tmp1:max;
            tmp1=tmp2;
        }
        cout<<max<<endl; 
    }  
}

发表于 2017-05-06 16:31:34 回复(0)

pein531

由于去掉一个数a[i]之后会出现一个新的间隔a[i+1]-a[i-1]（1<=i<=n-2），因此我们看看这个新出现的间隔最小能有多小。拿到这个新出现间隔的最小值和原始数组的间隔最大值比较，输出大的那个就可以了（因为假如最大间隔仍然是原来的那个，删数就并不会改变最大间隔，最小还是它；否则就应该是新间隔中的最小值）。

n = int(input())
a = list(map(int, input().strip().split()))
maxDiff, tempMax = a[n] - a[n - 1], float('inf')
for i in range(1, n - 1):
    maxDiff = max(a[i] - a[i - 1], maxDiff)
    tempMax = min(a[i + 1] - a[i - 1], tempMax)
print(min(maxDiff, tempMax))

编辑于 2021-04-11 18:28:48 回复(0)

kestars

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();
            int[] array=new int[n];
            array[0]=sc.nextInt();
            int[] diffArray=new int[n];
            int max=0;
            for(int i=1;i<n;i++){
                array[i]=sc.nextInt();
                diffArray[i]=array[i]-array[i-1];
                if(diffArray[i]>max){
                    max=diffArray[i];
                }
            }
            int tempMax=Integer.MAX_VALUE;
            for(int i=1;i<n-1;i++){
                if((diffArray[i]+diffArray[i+1])<max){
                    tempMax=max;
                    break;
                }else{
                    if(tempMax>(diffArray[i]+diffArray[i+1]))
                        tempMax=(diffArray[i]+diffArray[i+1]);
                }
            }
            System.out.println(tempMax);
        }
    }
}

发表于 2018-10-10 19:02:23 回复(0)

牛客第一高情商boy

普通人写法

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();
         int[] a=new int[n];
         int[] k=new int[n-1];
         for(int i=0;i<n;i++){
             a[i]=sc.nextInt();         
         }
         for(int i=0;i<n-1;i++){
             k[i]=a[i+1]-a[i];
         }
         int d=getMax(k);
         int[] mind=new int[n-2];
         for(int i=0;i<n-2;i++){
             if(k[i]+k[i+1]<d){
                 mind[i]=d;
             }else{
                 mind[i]=k[i]+k[i+1];
             }
         }
         int mindis=getMin(mind);
         System.out.println(mindis);
         }
       
     }
     public static int getMax(int[] arr)  
     {  
         int max = arr[0];  
         for(int i=0;i<arr.length;i++)  
         {  
             if(arr[i]>max)  
                 max = arr[i];  
         }  
         return max;  
     }  
      public static int getMin(int[] arr)  
     {  
         int min = arr[0];  
         for(int i=0;i<arr.length;i++)  
         {  
             if(arr[i]<min)  
                 min = arr[i];  
         }  
         return min;  
     }  
 }

发表于 2018-04-11 23:05:48 回复(0)

蓝魔4

模拟整个求值的过程，然后找出最小值就可以了！
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
		vector<int> input(n);
		for(int i=0;i<n;i++)
			cin>>input[i];
		vector<int> small;
		int max;
		for(int i=1;i<n-1;i++)
		{
			max=-1000000;
			for(int j=1;j<n;j++)
			{
				int k=j-1;
				if(j==i)
					j++;
				if(input[j]-input[k]>max)
					max=input[j]-input[k];
			}
			small.push_back(max);
		}
		max=small[0];
		for(int i=0;i<small.size();i++)
		{
			if(small[i]<max)
				max=small[i];
		}
		cout<<max<<endl;
	}
	return 0;
}

发表于 2017-06-27 15:02:59 回复(0)

Aurora1

while 1:
    try:
        s = raw_input()
        n = int(s)
    except:
        break
    d = map(int, raw_input().split())
    for i in range(0, n - 1):
        d[i] = d[i + 1] - d[i]
    d.pop()
    x, m = max(d), 0x7fffffff
    for i in range(0, n - 2):
        k = max(d[i] + d[i + 1], x)
        if k < m:
            m = k
    print m

发表于 2017-05-03 23:15:11 回复(0)

Alex-大伟

import java.util.ArrayList;
import java.util.Scanner;

//笨人只能想出笨方法
public class Mogu2 {

	/**
	 * @param args
	 */
	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[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = scanner.nextInt();
			}
			System.out.println(minOfMaxReDis(n, a));
		}
		
	}
	public static int minOfMaxReDis(int n, int[] a) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i=0;i<n;i++){
			list.add(a[i]);
		}
		int minReDis = Integer.MAX_VALUE;
		for(int i=1;i<=n-2;i++){
			int removeNum = list.remove(i);
			int mintemp= maxDis(list);
			if(mintemp < minReDis){
				minReDis = mintemp;
			}
			list.add(i, removeNum);
		}
		return minReDis;
	}
	public static int maxDis(ArrayList<Integer> list) {
		int maxDis = 0;
		for(int i=1;i<list.size();i++){
			int diff = list.get(i) - list.get(i-1);
			if(diff > maxDis){
				maxDis = diff;
			}
		}
		return maxDis;
	}
}

发表于 2016-09-28 09:23:23 回复(0)

菜鸟葫芦娃

动态规划的思想:求原序列的相邻元素的间隔值,合并相邻的间隔值,相当于删除原序列的元素。

1 2 3 7 8 最大间隔是 4 间隔值为[1,1,4,1]

* 删除2 [1,3,7,8] 最大间隔是4

* 删除3 [1,2,7,8] 最大间隔是5

* 删除7 [1,2,3,8] 最大间隔是5

* 又例如

1 3 5 8 11 12 最大间隔是3 间隔值为[2,2,3,3,1]

删除3 [1,5,8,11,12] 最大间隔是4

删除5 [1,3,8,11,12] 最大间隔是5

删除8 [1,3,5,11,12] 最大间隔是6

删除11 [1,3,5,8,12] 最大间隔是4

* 上面的例子告诉说明:删除一个元素后,剩余序列元素的间隔是原数组中相邻元素的差值合并后得到的新的间隔。

* 即求出原序列的相邻值,然后进行循环遍历,得到合并后的值和原序列的最大间隔进行比较,取的最小值

import java.util.Scanner;

public class Main {

* 1 2 3 7 8 最大间隔是 4

* 删除2 [1,3,7,8] 最大间隔是4

* 删除3 [1,2,7,8] 最大间隔是5

* 删除7 [1,2,3,8] 最大间隔是5

* 又例如

1 3 5 8 11 12 最大间隔是3

删除3 [1,5,8,11,12] 最大间隔是4

删除5 [1,3,8,11,12] 最大间隔是5

删除8 [1,3,5,11,12] 最大间隔是6

删除11 [1,3,5,8,12] 最大间隔是4

* 上面的例子告诉说明:删除一个元素后,剩余序列元素的间隔是原数组中相邻元素的差值合并后得到的新的间隔。

* 即求出原序列的相邻值,然后进行循环遍历,得到合并后的值和原序列的最大间隔进行比较,取的最小值

* */

 public static void main(String[] args) {  // TODO Auto-generated method stub  Scanner in = new Scanner(System.in);  while (in.hasNext()) {  int n = in.nextInt();  int[] arr = new int[n];  for (int i = 0; i < n; i++) {  arr[i] = in.nextInt();  }  process(arr, n);  }  in.close();  }  private static void process(int[] arr, int n) {  // TODO Auto-generated method stub  int maxInterval=-1;//记录原序列间隔的最大值  int minNewInterval=Integer.MAX_VALUE;//记录新的最大间隔  int [] dp=new int[n-1];//记录相邻两个元素的间隔  for(int i=1;i<=n-1;i++)  {  dp[i-1]=arr[i]-arr[i-1];  if (dp[i-1]>maxInterval) {  maxInterval=dp[i-1];   }  }  //原序列的间隔进行合并相当于删除原素,当大于maxInterval的时候选取最小值  for (int i = 0; i < dp.length-1; i++) {  int merge=dp[i]+dp[i+1];  if (merge>maxInterval) {  minNewInterval=Math.min(minNewInterval, merge);  }  else {  minNewInterval=Math.min(minNewInterval, maxInterval);  }  }  System.out.println(minNewInterval);  }
}

发表于 2016-09-27 09:03:50 回复(0)

C r 7

/*
循环删掉数组中的一个元素，将新数组存在arr1中，再将其赋给temp数组。算出temp数组中每个差值
求出最大的差值，放在value数组中，最后在value数组中找出最小的值输出。
*/
import java.util.Scanner;
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];
			for(int i=0;i<arr.length;i++){
				arr[i] = in.nextInt();
			}
			System.out.println(getValue(arr));
			
		}
	}
	public static int getValue(int[] arr){
		int result = 100;
		//删除后的间隔数组
		int[] value = new int[arr.length-2];
		int[] temp = new int[arr.length-1];
		for(int i=1;i<arr.length-1;i++){
			int[] arr1 = new int[arr.length-1];
			for(int m=0;m<i;m++){
				arr1[m] = arr[m];
			}
			for(int j=i+1;j<arr.length;j++){
				arr1[j-1] = arr[j];
			}
			for(int k=0;k<temp.length;k++){
				temp[k] = arr1[k];
			}

			int max = 0;
			for(int l=1;l<temp.length;l++){
				int cha = temp[l] - temp[l-1];
				if(cha > max){
					max = cha;
				}
			}
			value[i-1] = max;
		}
		for(int i = 0;i<value.length;i++){
			if(value[i] < result){
				result = value[i];
			}
		}
		return result;
	}
}

发表于 2016-09-18 21:06:00 回复(0)

CiaoLiang

#include<stdio.h>
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

int main(){
    int N;
    while(cin>>N){
        vector<int> Num(N,0);
        int MaxGap = INT_MIN;
        int ret = INT_MAX;
        for(int i=0; i<N; ++i){
            cin >> Num[i];
        }
        for(int i=0; i<N-1; ++i){
            MaxGap = max(MaxGap,Num[i+1]-Num[i]);
        }
        for(int i=1; i<=N-2; ++i){//最大值只会出现在MaxGap和a[i+1]-a[i-1]中
            int temp = max(Num[i+1]-Num[i-1],MaxGap);//消除i的结果
            ret = min(ret,temp);//最小的最大间隔
        }
        cout << ret <<endl;
    }
    return 0;
}

发表于 2016-09-04 22:04:40 回复(0)

fight灬奋斗

这题最终的输出值一定是原始串的最大间隔或者次大间隔，只有在原始串的最大间隔为a₁-a₀ 或者a_n-1-a_n-2 （出现在首或者尾时）最终的输出值为次大值。

#include <iostream>
using namespace std;
int Count(int* p,int len){
    int max=0;
    for(int i=1;i<len;i++)
        if(max<p[i]-p[i-1]){
        	max=p[i]-p[i-1];
    	}
    return max;
}
int min(int a, int b){
    return a>b?b:a;
}
int main(){
    int N;
    while(cin>>N){
        int *p=new int[N];
        for(int i=0;i<N;i++)
            cin>>p[i];
        cout<<min(min(Count(p,N),Count(p+1,N-1)),Count(p,N-1))<<endl;
    }
    return 0;
}

编辑于 2016-08-25 18:54:30 回复(0)