题解 | #牛牛摆放花#

题意整理

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

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