【牛客编程巅峰赛S1第6场】牛牛摆放花

题目

有 n 朵需要摆放的花，每朵花高度都不一样。摆放方式：

1. 将这些花摆成首尾相接的圆形；
2. 为了美观，希望摆放的花“丑陋度”最小。
   “丑陋度”意思为在一个摆放序列中，相邻花高度差的最大值。

程序应返回在多个摆放花的序列中，最小的“丑陋度”。

解题思路

要想丑陋度最小，那么排列应该从低到高，再从高到低。

将 n 朵花进行排序。然后将数按顺序放置左右两边。

例如，排序后为 。
先确定高度最小的花 1，将 2 和 4 放到它的左右，即 。放 7 或 8 的话会相差很大。
然后，依次在左右放 7 和 8，即 。这样摆放丑陋度最小。

因为某朵花 要与两朵花 和 相邻，所以可以对排序后的花隔一个遍历，计算它们高度差的最大值。

注意当 时，只有两朵花，直接计算它们的高度差。

C++代码

class Solution {
public:
    /**
     * ​返回按照这些花排成一个圆的序列中最小的“丑陋度”
     * @param n int整型 花的数量
     * @param array int整型vector 花的高度数组
     * @return int整型
     */
    int solve(int n, vector<int>& array) {
        // write code here
        sort(array.begin(), array.end());
        int ans = 0;
        if(n==2){
            return array[1]-array[0];
        }
        for(int i=2; i<n; i+=2){
            ans = max(ans, array[i]-array[i-2]);
        }
        for(int i=3; i<n; i+=2){
            ans = max(ans, array[i]-array[i-2]);
        }
        return ans;
    }
};