题意整理
- n朵花排成一圈,现在要摆放好这些花,使得相邻花的高度差尽可能小(所有花的高度由一个数组给出)。
- 求这些花摆放好之后,相邻距离的最大值。
方法一(双端队列)
1.解题思路
为了使得相邻花的高度差尽可能小,那么一定是往圈里先放第一矮和第二矮的花,再在中间放上第三矮和第四矮的花,直到放完所有的花。也可以先放第一高和第二高的花,再放第三高和第四高的花,依次放完所有花。
基本步骤:
- 初始化双端队列,并对数组排序。
- 遍历数组,将当前数放在队头,下一个数放到队尾,直到放完所有的数。
- 计算队列中相邻元素间的绝对值,队头和队尾也视为相邻,取所有绝对值的最大值,即是所求的高度差的最大值。
动图展示:
2.代码实现
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回按照这些花排成一个圆的序列中最小的“丑陋度” * @param n int整型 花的数量 * @param array int整型一维数组 花的高度数组 * @return int整型 */ public int arrangeFlowers (int n, int[] array) { //初始化双端队列 Deque<Integer> queue=new ArrayDeque<>(); //排序 Arrays.sort(array); //遍历数组,将当前数放在队头,下一个数放到队尾 for(int i=0;i<n;i+=2){ queue.addFirst(array[i]); if(i+1<n){ queue.addLast(array[i+1]); } } //计算首尾元素绝对值 int res=Math.abs(queue.peekFirst()-queue.peekLast()); for(int i=1;i<n;i++){ int value1=queue.peekFirst(); queue.removeFirst(); int value2=queue.peekFirst(); //计算队列间相邻元素绝对值 res=Math.max(res,Math.abs(value1-value2)); } return res; } }
3.复杂度分析
- 时间复杂度:排序的时间复杂度为,其余两次遍历都是线性的,所以最终的时间复杂度为。
- 空间复杂度:需要额外大小为n的队列,所以空间复杂度为。
方法二(数学)
1.解题思路
思路和方法一差不多,只是不需要把所有数放到队列。当将数组排好序之后,只需要计算奇数位相邻元素间的绝对值,再计算偶数位相邻元素间的绝对值,最后统计所有绝对值的最大值,和方法一的操作效果一致,只是少了放入队列的过程,节省了空间。
2.代码实现
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 返回按照这些花排成一个圆的序列中最小的“丑陋度” * @param n int整型 花的数量 * @param array int整型一维数组 花的高度数组 * @return int整型 */ public int arrangeFlowers (int n, int[] array) { //排序数组 Arrays.sort(array); //只有两个数的情况 if(n==2) return array[1]-array[0]; int res=0; //统计奇数位最大绝对值 for(int i=2;i<n;i+=2){ res=Math.max(res,array[i]-array[i-2]); } //统计偶数位最大绝对值 for(int i=3;i<n;i+=2){ res=Math.max(res,array[i]-array[i-2]); } return res; } }
3.复杂度分析
- 时间复杂度:排序的时间复杂度为,其余两次遍历都是线性的,所以最终的时间复杂度为。
- 空间复杂度:不需要额外的空间,所以空间复杂度为。