题意整理

  • 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.复杂度分析

  • 时间复杂度:排序的时间复杂度为,其余两次遍历都是线性的,所以最终的时间复杂度为
    • 空间复杂度:不需要额外的空间,所以空间复杂度为