题目

给你一个由 n 个正整数组成的数组 nums 。

你可以对数组的任意元素执行任意次数的两类操作：

如果元素是 偶数 ，除以 2

例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]

如果元素是 奇数 ，乘上 2

例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

示例 1：输入：nums = [1,2,3,4] 输出：1

解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1

示例 2：输入：nums = [4,1,5,20,3] 输出：3

解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3

示例 3：输入：nums = [2,10,8] 输出：3

提示：n == nums.length

2 <= n <= 105

1 <= nums[i] <= 109

解题思路分析

1、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

func minimumDeviation(nums []int) int {
   intHeap := make(IntHeap, 0)
   heap.Init(&intHeap)
   minValue := math.MaxInt32
   for i := 0; i < len(nums); i++ {
      if nums[i]%2 == 1 { // 奇数x2=>变为偶数放入堆， 统一处理为偶数
         nums[i] = nums[i] * 2
      }
      heap.Push(&intHeap, nums[i])
      minValue = min(minValue, nums[i]) // 记录最小值
   }
   res := intHeap[0] - minValue
   for intHeap.Len() > 0 && intHeap[0]%2 == 0 { //  把最大偶数处理/2
      node := heap.Pop(&intHeap).(int)
      minValue = min(minValue, node/2)
      heap.Push(&intHeap, node/2)
      res = min(res, intHeap[0]-minValue) // 目标结果：将最大值除以2，用最大值减去最小值
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

type IntHeap []int

func (h IntHeap) Len() int {
   return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
   return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
   *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
   value := (*h)[len(*h)-1]
   *h = (*h)[:len(*h)-1]
   return value
}

总结

Hard题目，使用堆解决