首页 > 试题广场 >

最大差值

[编程题]最大差值
  • 热度指数：1631 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个未排序的数列，找到此数列在已排序状态下的两个相邻值的最大差值，少于两个值时返回0。例如：给定数列 [1,3,2,0,1,6,8] 则 最大差值为3。注意：请尽量使用时间复杂度为O(n)的方案。

输入描述:
第一行输入单个整数N作为数列的大小，第二行输入所有数列中的元素M，共N个。0 < N <= 1000000, 0 < M < 2100000000


输出描述:
数列的最大差值
示例1

输入

3
1 10 5

输出

5
算法知识视频讲解
添加回答
曦姐跟班头像 曦姐跟班 

#include<iostream>
#include<vector>
using namespace std;
//
//来自邹博
//设n个数最大值max,最小值min
//n个数  分布 max,min共有n-1个区间
//每个区间内只需要统计最大和最小值即可
//每个区间[a,b),n个桶，最大数单独一个区间

int main()
{
	int n; cin >> n;
	vector<int> a(n, 0);
	int max = 0, min = 2100000000;
	vector<int> bucket_min(n, 2100000000), bucket_max(n, 0);
	
	for (auto &i : a)
	{
		cin >> i;
		if (i < min)min = i;
		if (i > max)max = i;
	}
	if (n == 1) { cout << 0; return 0; }
	double delta = ((double)max - min) / (n - 1);
	if (delta == 0) { cout << 0; return 0; }
	for (auto i : a)
	{
		int index = (i - min) / delta ;
		if (bucket_min.at(index) >= i)bucket_min.at(index) = i;
		if (bucket_max.at(index) <= i)bucket_max.at(index) = i;
	}
	int max_delta = 0;
	int begin_1 = bucket_max[0];
	for (int i = 1; i < n; i++)
	{
		if (bucket_min[i] != 2100000000 && (bucket_min[i] - begin_1 > max_delta))//这个区间有数
			max_delta = bucket_min[i] - begin_1;
		if(bucket_max[i]!=0)begin_1 = bucket_max[i];
	}
	cout << max_delta;



}

编辑于 2017-08-29 23:58:59 回复(0)
Java
开心超人129267头像 开心超人129267 
public class LongestDistance {

    public int getDis(int[] A, int n) {
        // 定义两个数组, leftMin 和 rightMax, 其中 leftMin[i] 表示从 0 到 i 之间的最小值,
        // rightMax[i] 表示从 n-1 到 i 之间的最大值.
        // 之后利用 rightMax[i] - leftMin[i] 得到差的最大值

        int[] leftMin = new int[n];
        int[] rightMax = new int[n];
        leftMin[0] = A[0];
        rightMax[n - 1] = A[n - 1];

        for (int i = 1; i < n; ++i) {
            if (leftMin[i - 1] < A[i]) {
                leftMin[i] = leftMin[i - 1];
            } else {
                leftMin[i] = A[i];
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (rightMax[i + 1] > A[i]) {
                rightMax[i] = rightMax[i + 1];
            } else {
                rightMax[i] = A[i];
            }
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (rightMax[i] - leftMin[i] > res) {
                res = rightMax[i] - leftMin[i];
            }
        }
        return res;
    }
}
发表于 2018-09-06 08:45:14 回复(0)
C/C++
天蓝何头像 天蓝何 
// 分享一个伪O(n)的算法，用map存储每个不同值，然后遍历，这里用到了map遍历时其键从小到大的特点
#include <iostream>
#include <map>
using namespace std;
int main(){
    int n;
    int max;
    cin >> n;
    map<int,int> m;
    int x;
    for(int i=0;i<n;++i){
        cin >> x;
        ++m[x];
    }
    
    map<int,int>::iterator it = m.begin();
    ++it;
    max = 0;
    map<int,int>::iterator pre = m.begin();
    for(;it!=m.end();++it,++pre){
        if(it->first - pre->first > max)
            max = it->first - pre->first;
    }
    cout << max;
    return 0;
}

发表于 2017-08-17 22:56:54 回复(4)
哇咔哇咔头像 哇咔哇咔 
//先排序，再直接开一个数组保存相邻元素差值，找最大的就行了，时间复杂度O(n),简单暴力。
//运行时间68ms，占内存1920K。感觉68ms有点长，时间复杂度大于O(n),感谢“我要offer~”的意见。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    int N;
    while(cin>>N){
        vector<int> array(N);
        for(int i=0;i<(int)array.size();++i){
            cin>>array[i];
        }         
        sort(array.begin(),array.end());
        vector<int> minu(N);//相邻元素差值
        minu[0]=0;
        int max_minu=0;
        for(int i=1;i<(int)minu.size();++i){
            minu[i]=array[i]-array[i-1];
            max_minu=minu[i]>max_minu?minu[i]:max_minu;
        }
        cout<<max_minu<<endl;
    }
    return 0;
}

编辑于 2017-08-09 18:51:15 回复(2)
⎝≧⏝⏝≦⎠|头像 ⎝≧⏝⏝≦⎠|
有没有大佬解一下，前面有个一样的，但数组大小小于500，这个数组有点大，桶排序肯定不行了。
发表于 2017-08-03 21:15:17 回复(1)
牛客6287812号头像 牛客6287812号
(｡･ω･｡)ﾉ♡::i:ω･:::｡):ﾉ‘♡:‘::i
发表于 2017-08-02 18:31:34 回复(0)
牛豆ADOL头像 牛豆ADOL
*** 写个有100000个输入，最后才给100个左右。怪不得数组越界。
发表于 2021-08-23 23:58:45 回复(0)
Mongolia-Duck-king头像 Mongolia-Duck-king
思路就是排序后对每两个相邻元素做差，然后比较

N=int(input())
ls=list(map(int,input().split(' ')))
ls.sort(reverse=False)       #排序
res = ls[1] - ls[0]         #首先算出前两个的差
for i in range(len(ls)-1):      #比较后续相邻的差，比res大就替换
    if ls[i+1]-ls[i] > res:
        res = ls[i+1] - ls[i]
print(res)
发表于 2019-09-02 17:54:00 回复(0)
四十平米头像 四十平米 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) 
                if (in.hasNextInt())
                    a[i] = in.nextInt();
            if (n == 1) {
                System.out.println(0);                                  
                return;
            }
            Arrays.sort(a);
            int d = 0;
            for (int i = 0; i < n - 1; i++) {
                d = Math.max(d, a[i+1]-a[i]);
            }
            System.out.println(d);
       // }
    }
}

发表于 2018-09-02 22:06:58 回复(0)
starboycn头像 starboycn
用优先队列来代替排序 
#include <bits/stdc++.h>

using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    if(N < 0) return 0;
    priority_queue<int, vector<int>, greater<int>> heap;
    int tmp;
    while(~scanf("%d", &tmp)){
        heap.push(tmp);
    }
    
    int cur = heap.top();
    heap.pop();
    int res = 0;
    while(!heap.empty()){
        tmp = heap.top();
        heap.pop();
        res = max(res,tmp - cur);
        cur = tmp;
    }
    cout<<res;
    return 0;
    
}



发表于 2021-07-05 16:10:40 回复(1)
Java
牛客150138644号头像 牛客150138644号
第三组测试数据有问题
发表于 2023-08-30 09:43:20 回复(0)
我敢说神马头像 我敢说神马 
//我的想法：直接基数排序思想，牺牲空间，复杂度o(n)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    int num;
    int max_num = 0;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        if(max_num<num)
        {
            max_num = num;
        }
        a.push_back(num);
    }
    vector<bool>c;
   //根据输入数据的最大值开辟一个vector
    c.resize(max_num+1);
    for(int i=0;i<n;i++)
    {
        if(c[a[i]]==0)
        {
            c[a[i]] =1;
        }
    }
    int max =-1;
    int j=0;
   //寻找差距最大的相邻数
    for(int i=2,j=1;j<=max_num&&i<=max_num;)
    {
        while(i<=max_num&&c[i]==0)
        {
            i++;
        }
        while(j<=max_num&&c[j]==0)
        {
            j++;
        }
        if(i==max_num+1||j==max_num+1)
        {
            break;
        }
        if(i-j>max)
        {
            max = i-j;
        }
        j=i;
        i++;
    }
    cout<<max;
    return 0;
}

发表于 2018-03-28 19:43:18 回复(0)
1000把影魔头像 1000把影魔 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <math.h>
#include <algorithm>

using namespace std;



int main(int argc, char **argv)
{
	int cnt;
	while (cin>>cnt)
	{
		vector<int> nums(cnt);
		for (int i = 0; i < cnt; i++)
			cin >> nums[i];
		
		sort(nums.begin(), nums.end());
		int smax = -9999, sub = 0;
		for (int i = 0; i < nums.size() - 1; i++)
		{
			sub = nums[i + 1] - nums[i];
			smax = sub > smax ? sub : smax;
		}
		cout << "" << smax << endl;
	}

	return 0;
}

发表于 2017-09-11 10:58:58 回复(0)
牛客594283号头像 牛客594283号
#include<iostream>
using namespace std;
voidquickSort(ints[], intl, intr);
intmain(){
    intN;
    cin>>N;
    int*M = newint[N];
    //int t = 2100000000;
    //cout<<t;
    for(inti = 0; i < N;i++){
        cin>>M[i];
    }
    quickSort(M,0,N - 1);
    if(N < 2){
        return0;
    }
    intMaxSub = M[1] - M[0];
    for(inti = 2; i < N;i++){
        if(M[i] - M[i - 1] > MaxSub){
            MaxSub = M[i] - M[i - 1];
        }
    }
    cout<<MaxSub<<endl;
    return0;
}
voidquickSort(ints[], intl, intr) 
{ 
    if(l< r) 
    {       
        inti = l, j = r, x = s[l]; 
        while(i < j) 
        { 
            while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 
                j--;  
            if(i < j) 
                s[i++] = s[j]; 
            while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 
                i++;  
            if(i < j) 
                s[j--] = s[i]; 
        } 
        s[i] = x; 
        quickSort(s, l, i - 1); // 递归调用 
        quickSort(s, i + 1, r); 
    }  
}

发表于 2017-08-29 21:23:56 回复(0)
Python
傻妞妞-MM头像 傻妞妞-MM 
import sys
n = int(sys.stdin.readline().strip()) def maxnum(initlist):
    li = []
    n = len(initlist) for i in range(n):
        num = initlist[i] - initlist[i-1]
        li.append(num) return max(li)
initlist = list(map(int, sys.stdin.readline().strip().split()))
initlist = sorted(initlist)
result = maxnum(initlist) print result
发表于 2017-08-25 13:12:45 回复(0)
jokervsbat头像 jokervsbat
总是这样
答案错误:您提交的程序没有通过所有的测试用例
case通过率为66.67%

测试用例:
100000

对应输出应该为:

5089

你的输出为:
空。请检查一下你的代码，有没有循环输入处理多个case。
发表于 2017-08-18 17:34:54 回复(1)
担担面1头像 担担面1

//为什么只通过了66.67%！！！ 。。。
import java.util.*;
public class Main{

public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int datanum = in.nextInt();
int[] data = new int[datanum];
for (int i = 0; i < data.length; i++) {
data[i] = in.nextInt();
}
int maxDis = findMaxDisfromArray(data,datanum);
System.out.println(maxDis);
}

}

private static int findMaxDisfromArray(int[] data ,int datanum) {
if (data == null || data.length < 2) {
return 0;
}
int len = data.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, data[i]);
max = Math.max(max, data[i]);
}
if (min == max) {
return 0;
}

boolean[] hasNum = new boolean[datanum + 1];
int[] maxs = new int[datanum + 1];
int[] mins = new int[datanum + 1];

int bid = 0;
for (int i = 0; i < datanum; i++) {
bid = bucket(data[i], datanum, min, max); // 算出桶号
mins[bid] = hasNum[bid] ? Math.min(mins[bid], data[i]) : data[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], data[i]) : data[i];
hasNum[bid] = true;
}

int res = 0;
int lastMax = 0;
int i = 0;
while (i <= datanum) {
if (hasNum[i++]) { // 找到第一个不空的桶
lastMax = maxs[i - 1];
break;
}
}
for (; i <= datanum; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;

}
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}

}

发表于 2017-08-12 12:29:17 回复(0)
chensongchao头像 chensongchao 
//桶排序时间复杂度O(n)
#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int min;
    int max;
    Node(int _min=2100000000, int _max=-1):min(_min), max(_max){}
};

int main(){
    int n;
    while (cin >> n){
        vector<int> arr(n);
        int tmp;
        int min = 2100000000;
        int max = -1;
        int i;
        for (i = 0; i<n; i++){
            cin >> tmp;
            arr[i] = tmp;
            min = tmp < min ? tmp : min;
            max = tmp > max ? tmp : max;
        }
        int step = (max - min+1)/n ;
        if ((n*step - (max - min + 1) != 0))
            step++;
        vector<Node> buck(n);
        for (i = 0; i<n; i++){
            int index = (arr[i] - min)/step;
            buck[index].min = arr[i] < buck[index].min ? arr[i] : buck[index].min;
            buck[index].max = arr[i] > buck[index].max ? arr[i] : buck[index].max;
        }
        i = 0;
        while (i<n && buck[i].max == -1){
            ++i;
        }
        int ans = 0;
        int last = buck[i++].max;
        while (i<n){
            while (i<n && buck[i].min == 2100000000)
                i++;
            ans = buck[i].min - last > ans ? buck[i].min - last : ans;
            last = buck[i].max;
            i++;
        }
        cout << ans << endl;
    }
    return 0;
}
发表于 2017-08-12 00:34:43 回复(0)
C/C++
GodRay头像 GodRay
这题要求O(n)复杂度，用到STL、Java中的排序算法的都不会满足时间复杂度要求，虽然C++用sort也能过。这题用桶排序思想做，m个数字，开辟m+1个桶，每个桶容纳量为(max-min) / n，第n+1个放最大值。m+1个桶内必有一个空桶。每个数字放到对应的桶内，相邻最大差值就是那个隔着一个或多个空桶的数字之差。牺牲空间换取时间
发表于 2017-08-10 21:38:58 回复(1)
我要offer~头像 我要offer~ 
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[] data = new int[n];
            for (int i = 0; i < n; i++)
                data[i] = in.nextInt();
            System.out.println(MaxDis(data, n));
        }
        in.close();
    }
     
    public static int MaxDis(int[] A, int n) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            max = Math.max(A[i], max);
            min = Math.min(A[i], min);
        }
        int d = (max - min) / n;
        int[] Max = new int[n + 1];
        int[] Min = new int[n + 1];
        Max[0] = Min[0] = min;
        Max[n] = Min[n] = max;
        for (int i = 0; i < n; i++) {
        	if (A[i] != max && A[i] != min) {
        		Max[(A[i] - min) / d] = Math.max(Max[(A[i] - min) / d], A[i]);
                if (Min[(A[i] - min) / d] == 0)
                    Min[(A[i] - min) / d] = A[i];
                else
                    Min[(A[i] - min) / d] = Math.min(Min[(A[i] - min) / d], A[i]);
        	}
        }
        int count = 0;
        int res = 0;
        int start = 1;
        for (int i = 1; i < n; i++) {
            count = 0;
            while (Max[i] == 0) {
                count++;
                i++;
                start = i;
            }
            res = Math.max(count, res);
        }
        return Min[start] - Max[start - res - 1];
    }
}

谁能告诉我总说只能测试一个用例什么鬼，我明明有while(in.hasNext())的啊
发表于 2017-08-09 23:31:27 回复(3)
提交观点

问题信息

C++工程师 2017 数组 吉比特 Java工程师
难度：
25条回答 6876浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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