庆祝61
牛家庄幼儿园为庆祝61儿童节举办庆祝活动,庆祝活动中有一个节目是小朋友们围成一个圆圈跳舞。牛老师挑选出n个小朋友参与跳舞节目,已知每个小朋友的身高h_i。为了让舞蹈看起来和谐,牛老师需要让跳舞的圆圈队形中相邻小朋友的身高差的最大值最小,牛老师犯了难,希望你能帮帮他。
如样例所示:
当圆圈队伍按照100,98,103,105顺时针排列的时候最大身高差为5,其他排列不会得到更优的解
输入描述
输入包括两行,第一行为一个正整数n(3 ≤ n ≤ 20)
第二行为n个整数h_i(80 ≤ h_i ≤ 140),表示每个小朋友的身高。
输出描述
输出一个整数,表示满足条件下的相邻小朋友身高差的最大值。
输入例子1
4
100 103 98 105
输出例子
5
思路：
将相邻大小的元素放在一起，小的站中间，大的站两边（或者大的站中间小的站两边）
import java.util.*;
public class Main{
public static void main(String [] args){
Scanner scanner =new Scanner(System.in);
int number = scanner.nextInt();
int index = 0;
int [] value = new int[number];
while(index<number){
value[index++] = scanner.nextInt();
}
Arrays.sort(value);
//队列
Queue<Integer> queue = new LinkedList<Integer>();
//栈
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<value.length;i++){
if(i%2==0)
queue.offer(value[i]);
else
stack.push(value[i]);
}
index = 0;
//更新数组元素位置
while(!stack.empty()){
value[index++] = stack.pop();
}
while(queue.size()!=0){
value[index++] = queue.poll();
}
int max = Integer.MIN_VALUE;
for(int i = 1;i<value.length;i++){
index= value[i]>=value[i-1]?value[i]-value[i-1]:value[i-1]-value[i];
if(index>max)
max = index;
}
index = value[value.length-1]>=value[0]?value[value.length-1]-value[0]:value[0]-value[value.length-1];
if(index>max)
max = index;
System.out.println(max);
}
}