发表于 2024.05.26

• 一个需要点巧思的分治构造题目，如何将一个漂亮数组分解为两个漂亮子数组A和B的构造，且对于任一选取于漂亮数组A的元素a和任一选取于漂亮数组B的元素b(即两端分别选择于不同的子数组)，均不存在a + b = 2 * c的情况。这里的c是a和b之间的任意元素。通过观察可以知道，对于一个等差数组，我们将奇数位置的元素放在子数组A，偶数位置的元素放在子数组B，则可以满足题目要求。因为对于任意的满足上述选取要求的a和b，c不会存在于该数组中。因此，我们可以通过递归的方式构造漂亮数组。

  class Solution:
      def beautifulArray(self, n: int) -> List[int]:
          ans = [-1] * n
  
          def build(l: int, r: int, arr: List[int]):
              if l == r:
                  ans[l] = arr[0]
                  return
              odd = arr[1::2]
              even = arr[::2]
              build(l, l + len(odd) - 1, odd)
              build(l + len(odd), r, even)
  
          build(0, n - 1, list(range(1, n + 1)))
          return ans

• LC 题目链接