题目陈述

  • 大意：n朵花排成一圈，最小化相邻两朵花高度差的最大值，输出最大值。
  • 约定：将所求值成为丑陋值，即要求最小的丑陋值

    算法一：暴力做法

    算法思路

  • 因为已经知道了有n个数字，我们只需要生成这n个数字的所有排序
  • 然后依次计算每个序列的丑陋值，依次更新ans，求出最小的即可

    代码实现

    class Solution {
public:
  int arrangeFlowers(int n, vector<int>& a) {
      sort(a.begin(),a.end());//排序 
      int ans=1e9;//ans初值需要足够大，才能保证第一次就被更新掉 
      do{
          int now=abs(a[n-1]-a[0]);//因为是一个圆排列，首位也要 
          for(int i=0;i<n-1;i++){
              now=max(now,abs(a[i]-a[i+1]));//寻找最大差值 
          }
          ans=min(now,ans);//看看是否是更小的丑陋值 
      } while(next_permutation(a.begin(),a.end()));//继续生成下一个排序 
      return ans;
  }
};

    复杂度分析

  • 时间复杂度,构造了所有排序，乘法原理易得为
  • 空间复杂度，定义了ans,now，为

    算法二：构造法+双端队列

    性质引入

  • 此处我们想用逆向思维，来倒推他的性质
  • 依旧先跟大家说一下结论，再来证明：如果我们将这个环，从最大值处断开（把最大值处变为链的左端），那么这条链必然是先递减再递增的

    结论证明

  • 我们假设，序列中是否有可能有一处或者几处地方，出现”波浪形“（先增后减再增）?
  • 答案是不可能的，下面我给大家解释一下
  • 如果出现了这种情况,，避免用太抽象的语言，我给大家举个例子，如下图
    在这里插入图片描述

  • 如果我们将3,4交换，将”波浪形“调整为”单调型“
    在这里插入图片描述

  • 那么可以发现，将{3,4}看做一个整体，4在9旁边的差值明显比3在9旁边来的小，3在2旁边的差值也比4在2旁边的差值小

  • 对于最大值来说，我们要构造”单调型“，只能两边都是递减，这样整个序列的类型性质也就被确定了下来

  • 所以我们应该构造

    ^型

  • 这样的序列，（当然对于最小值构造”V“形也是一样的）

  • 故从从最大值处断开（把最大值处变为链的左端），那么这条链必然是先递减再递增的，得证

    算法思路

  • 既然我们知道了性质，那么我们要构造，显然就不难了

  • （注意：上面我举得例子没按这个来构造，只是为了证明性质）

    最大值处来构造

  • （注意：此处的数组a为排序过的）

  • 既然我们构造的是

    ^型

  • 那么我们显然应该围绕最大值来做，我们借助双端队列，先放入最大值a[n]

  • 要使最大值两端的数最小，不难看出应该左右各应该放入a[n-1],a[n-2]

  • 接下来我们又要让a[n-1],a[n-2]最小

  • 先考虑a[n-1],因为a[n-2]也被选取了，所以我们只能选择a[n-3]

  • 再考虑a[n-2]，不难想到填写的是a[n-4]

  • 此处我们以及看出规律了，从大到小取数字，双端队列前后各放入一个数，这样得到的就是最优的答案

最小值处来构造

  • 其实跟上面大同小异
  • 构造为

    V形

  • 从小到大取数字，双端队列前后各放入一个数，这样得到的也是最优的答案

    代码实现

  • 以下为最大值处来构造
    class Solution {
public:
  int arrangeFlowers(int n, vector<int>& a) {
      sort(a.begin(),a.end());//排序 
      deque<int> d;//双端队列 
      for(int i=n-1;i>=0;i--){//从小到大取数字 
          d.push_back(a[i--]);//放入尾 
          if(i>=0)d.push_front(a[i]); //放入头           
      }
      int ans=abs(d.front()-d.back());//圆排列还需要计算头尾的 差值 
      int head;
      for(int i=1;i<n;i++){
          head=d.front();
          d.pop_front();//双端队列不能直接访问，得先取出来 
          ans=max(ans,abs(head-d.front()));//计算相邻两个数的差值 
      }
      return ans;
  }
};

    复杂度分析

  • 时间复杂度,排序数组为，构造答案序列、求差值都为，总得为
  • 空间复杂度，定义了双端队列，为

    算法三：性质法

    算法思路

  • 算法三本质上面跟算法二没有差别，只是算法二的改进
  • 我们可以从上述结论中发现，构造好的序列，除了最大值处，有个跟a[n-1]相邻的，其余的数的左右邻居，都是跟自己差值为2的（a[0],a[1]其实在头尾，最后会接起来）
  • 但是a[n]和a[n-1]、a[n-2]谁的差值大，显然是a[n-2]，a[0]和a[1]、a[2]谁的差值大，显然是a[2]
  • 所以我们只需要通过排序后下标差值为2的数的差值即可求出答案

    代码实现

    class Solution {
public:
  int arrangeFlowers(int n, vector<int>& a) {
      if(n==2){//特判两个数的情况 
          return abs(a[1]-a[0]);
      }
      sort(a.begin(),a.end());//排序 
      int ans=0;
      for(int i=2;i<n;i+=2)ans=max(ans,a[i]-a[i-2]);//下标为偶数的 
      for(int i=3;i<n;i+=2)ans=max(ans,a[i]-a[i-2]);//下标为奇数的 
      return ans;
  }
};

    复杂度分析

  • 时间复杂度,排序数组为，求差值为，总得为
  • 空间复杂度，定义了ans，为