You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

• If the element is even, divide it by 2.
  • For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].
• If the element is odd, multiply it by 2.
  • For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

Constraints:

• n == nums.length
• 2 <= n <= 105
• 1 <= nums[i] <= 109

HARD 难度的题目总是让我头痛：它们常常需要想到一些特定的思路，很难代表一类题目。但是，它们又确实会用到一些常用的知识点。这让我感到犹豫：我是否该记录它们？尤其它们已经大大超出了我目前的水平。

这一题被记录下来有一个有趣的原因，稍后再说。

首先，我们可以很容易发现，一旦数字被放大（*2），它们就不能继续放大了。于是解题思路就是把所有数都先*2，这样就不用考虑放大这种情况。

接下来，我们维护一个有先队列，每次把最大的数收窄（/2）。当我们无法收窄，也就是最大值为奇数的时候，就可以得出结果了。

单纯想到这里已经非常困难，对得起HARD难度。而JS解这题甚至更难，因为JS是没有内置优先队列API的！

一开始的时候我遍历整个数组（由于数组是排过序的，线性时间寻找插入位置很简单），结果超时了。随后看了下答案得到启示，使用分治法找到插入点。随后也自然遇到了分治法管理的边际条件问题。我从来没有成功搞清楚国分治法的边际条件要怎么稳定、不出错地解决，这也是我讨厌分治法的原因！不管怎么样，题解在时间限制内……

那么，为了比较好地解决这道题目，需要一个好地优先队列实现。难不成要专门为了这题自己实现一个大根堆？想想都觉得吐血。但是优先队列又是那么常见。到头来还是准备一个比较简单的实现好了……

附写出的解：

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeviation = function(nums) {
    let difference = Infinity

    nums = nums.map(n => isOdd(n) ? n*2 : n).sort((a, b) => a-b)
    while(!isOdd(nums[nums.length-1])) {
        let max = nums.pop()
        
        max = max/2
        
        if (nums[0] > max)
            nums.unshift(max)
        else if (nums[nums.length-1] < max)
            nums.push(max)
        else {
            let left = 0, right = nums.length-1
        
            while(right - left > 1) {
                const mid = Math.floor((right + left) / 2)
                if (nums[mid] < max) {
                    left = mid
                } else {
                    right = mid
                }
            }
            
            nums.splice(right, 0, max)
        }
        difference = Math.min(nums[nums.length-1] - nums[0], difference)
    }
    
    return difference
    
    function isOdd(num) {
        return num % 2
    }
};