给定一个递增序列，a1 <a2 <...<an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少？
[编程题]最大间隔
最开始考虑这个间隔值就是两个间隔的最大值是有问题的，虽然能够通过，但是解决不了如：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)
分为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();
}
}
}
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)
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)
//最大间隔的最小值实际就是原来数组相邻元素间隔的最大值
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)
输入的时候记录所有的差值并保存在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)
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)
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)
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)
链接：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)
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)
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)
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)
问题信息
通过挑战的用户
查看代码-
2022-09-14 14:38:38 -
2022-09-13 15:36:34
-
2022-09-13 15:30:45 -
2022-09-12 15:39:29
-
2022-09-09 22:03:34
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
