思路

题目分析

1. 题目给出数组的大小，同时给出了一个数组
2. 题目规定数组中元素表示花高
3. 题目的数组围成一圈，相邻元素的差值最大值作为这个圈的丑陋值
4. 我们要合理排序这个圈中的元素，使这个圈的丑陋值最小
5. 返回这个圈的最小丑陋值

• 方法一：暴力（超时）
  • 枚举出来所有的排序方案
  • 逐个计算出每个圈的丑陋值
  • 选出最小的丑陋值
  • 时间代价巨大
• 方法二：贪心数学性质
  • 我们可以想到这个圈在数组的表现形式应该是先递增，后递减
  • 因此排序很重要
  • 排序后，将奇数位的元素统一移到前面，偶数位的元素统一移到后面
    • 奇偶交替一前一后向中间逼近，使得中间的值是最大的
    • 这样做的原因是我们需要丑陋值最小，而丑陋值是和相邻元素之间的差值有关
    • 我们只有将递增顺序的全序列一奇一偶地拆分重新排列到数组首尾，才能保证最新的序列相邻元素之间的差值被降到最小
    • 否则按照其他方法排列的新序列，丑陋值这个差值只能大于上述安排方案
  • 这样贪心地形成了先递增后递减的序列
  • 计算出来的圈丑陋值就是最小的

贪心证明（给看不懂上面文字描述的同学具体推理一下）：

• 假设存在一组递增的序列$a_1,a_2,a_3,...,a_{n}a\_1,a\_2,a\_3,...,a\_n$a1​,a2​,a3​,...,an​，我们将其按照上述贪心策略进行安排之后会形成的序列为$a_1,a_3...,a_n,...,a_4,a_{2}a\_1,a\_3...,a\_n,...,a\_4,a\_2$a1​,a3​...,an​,...,a4​,a2​，因此此时丑陋值我们可以计算为$max(\mid a_1-a_2\mid ,\mid a_{i+2}-a_i\mid ,\mid a_n-a_{n-1}\mid (如果n为偶数，n为奇数则无此项\left)\right)max(|a\_1-a\_2|,\; |a\_\{i+2\}-a\_\{i\}|,\; |a\_\{n\}-a\_\{n-1\}|(如果n为偶数，n为奇数则无此项))$max(∣a1​−a2​∣,∣ai+2​−ai​∣,∣an​−an−1​∣(如果n为偶数，n为奇数则无此项))。
• 根据题意，按照这种方法排序的结果我们将其视作一个环状序列，首尾要相接，因此如果这个排列的整体前后错位了也是不影响的。
• 我们使用反证法证明结论
• 假设如果我们不按照此顺序排列（环状呈现的结果不同），则必定会出现有相邻的两个元素存在$\mid a_i-a_j\mid (i-j>2)|a\_\{i\}-a\_\{j\}|(i-j>2)$∣ai​−aj​∣(i−j>2)比$\mid a_{i+2}-a_i\mid |a\_\{i+2\}-a\_\{i\}|$∣ai+2​−ai​∣要大，因此丑陋值一定比上面的$maxmax$max计算出来的大，因此得证

方法一：暴力（超时）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int arrangeFlowers(int n, vector<int>& array) {
        // write code here
        int res = INT_MAX;
        while(next_permutation(array.begin(), array.end())) {    // 遍历所有的排序方案
            int val = abs(array[0] - array[n-1]);                // 围成一圈后首位元素要计算一次
            for(int i = 0; i < n-1; i++) val = max(val, abs(array[i+1] - array[i])); // 其他元素相邻高度差也要计算
            res = min(res, val);    // 从每一躺的丑陋值中选出最小的丑陋值
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(N!)O(N!)$O(N!)，所有的的排序方案全部要进行
• 空间复杂度：$O\left(1\right)O(1)$O(1)，使用了常量级别的空间大小

方法二：贪心数学性质

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int arrangeFlowers(int n, vector<int>& array) {
        // write code here
        int cnt[n];
        sort(array.begin(), array.end());            // 对原数组排序
        int l = 0;                                   // 标记左侧指针
        int r = n-1;                                 // 标记右侧指针
        for(int i = 0; i < n; i++) {                 // 对排序后的数据遍历
            if(i % 2 == 0) {                         // 偶数位置的数字重新放到最前面
                cnt[l++] = array[i];
            }
            else {                                   // 奇数位置的数字重新放到最后面
                cnt[r--] = array[i];
            }
        }
        
        int res = 0;
        for(int i = 0; i < n - 1; i++) {
            res = max(res, abs(cnt[i+1] - cnt[i]));    // 重新统计相邻元素高低岔开的最大高度值
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O\left(NlogN\right)O(NlogN)$O(NlogN)，主要时间代价消耗在排序上
• 空间复杂度：$O\left(N\right)O(N)$O(N)，使用了一个新的一维数组，量级和原数组大小一致