解決:配列の偏差を最小にする

これは一連のleetcode解決説明の一部です.あなたがこの解決法が好きであるか、それが役に立つとわかるならば、このポストと同様に/または上告my solution post on Leetcode's forumsをしてください.

Leetcode Problem #1675 (Medium): Minimize Deviation in Array
説明
n個の正整数の配列NUMが与えられます.
配列の任意の要素に対して任意の回数の2種類の操作を実行できます.

要素が偶数の場合、2で除算します.
例えば、

の場合、配列が[ 1 , 2 , 3 , 4 ]の場合、最後の要素でこの操作を行うことができます.

要素が奇数なら、2を掛けます.
例えば、

などの場合、配列が[ 1 , 2 , 3 , 4 ]の場合、最初の要素でこの操作を行うことができます.

配列のずれは、配列内の任意の2つの要素間の最大の違いです.
いくつかの数の操作を実行した後に配列が持つ最小の偏差を返します.
例:
例1 :
入力
nums =[ 1 , 2 , 3 , 4 ]
出力:
1
解説
配列を[ 1 , 2 , 3 , 2 ]、thento [ 2 , 2 , 3 , 2 ]に変換することで、偏差は3 - 2 = 1になります.
例2 :
入力
nums =[ 4 , 1 , 5 , 20 , 3 ]
出力:
3
解説
2つの演算の後に[ 4 , 2 , 5 , 5 , 3 ]に配列を変換することができます.
例3 :
入力
nums =[ 2 , 10 , 8 ]
出力:
3
制約

n = nums.長さ

2 <= n <= 105

1 <= nums [ i ] <= 109

考え
この場合のヒントは少し後方です.一度だけ乗算操作を実行することが可能であるので、(数が偶数になるので)、しかし、あなたは潜在的に分割操作を何度も実行することができます.
あなたが最小値から始めたならば、ヒントが示唆するように、あなたは上へ動く間、別々にその量を乗算しないように別々に各々の要素のために最大値を追跡しなければならないでしょう.
アイデアは実際にそこから非常に簡単です.それが偶数であるならば、各々のnums［i］のために最大可能な価値を見つけてください、そして、最大のものを取っておいて、2で割り続けてください.各ステップでは、新しい最高のANS(最高値-最低値)を見つけたかどうかを確認してください.最大数が奇数ならば、それはあなたが既に発見したより良い番号に到達することは不可能であることを意味2、それを分割することはできませんので、あなたのベスト広告を返します.
実装
ソートされたデータを必要としますが、最大値をいつでも変更する必要があります.NUMの最小値を必要としますが、実際にはその要素を変更する必要はありません.ですから、Minで行くことができます.
まず、NUMを使ってイテレータを繰り返す必要があります.
それから、ヒープ/PQの最大値が偶数である間、私たちはそれを取り出して、それを2で割ることができて、必要に応じて我々のANNとMINを更新して、ヒープ/PQにそれを再挿入することができます.
一旦ヒープ/PQの最上位で奇数に達するならば、最高の広告を返してください.
JavaScriptコードw/maxpriorityqueue () :
このコードは読みやすいが効率が悪い.LeetCodeはJavaScriptの実装でデフォルトで含まれているPriorityQueue NPMパッケージを利用します.

var minimumDeviation = function(nums) {
    let pq = new MaxPriorityQueue({priority: x => x})
    for (let n of nums) {
        if (n % 2) n *= 2
        pq.enqueue(n)
    }
    let ans = pq.front().element - pq.back().element
    while (pq.front().element % 2 === 0) {
        pq.enqueue(pq.dequeue().element / 2)
        ans = Math.min(ans, pq.front().element - pq.back().element)
    }
    return ans
};

JavaScriptコードw/maxヒープ実装:

var minimumDeviation = function(nums) {
    let len = nums.length, min = Infinity,
        heap = new Uint32Array(len+1), hix = 1
    heap[0] = 2e9

    const heapify = val => {
        let i = hix, par = i >> 1, temp
        heap[hix++] = val
        while (heap[par] < heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }

    const extract = () => {
        let max = heap[1], left, right, temp,
            i = 1, child = heap[3] > heap[2] ? 3 : 2
        heap[1] = heap[--hix], heap[hix] = 0
        while (heap[i] < heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] > heap[left] ? right : left
        }
        return max
    }

    for (let i = 0, n = nums[0]; i < len; n = nums[++i]) {
        if (n % 2) n *= 2
        if (n < min) min = n
        heapify(n)
    }
    let curr = extract(), ans = curr - min
    while (curr % 2 === 0) {
        curr /= 2
        if (curr < min) min = curr
        heapify(curr)
        curr = extract()
        ans = Math.min(ans, curr - min)
    }
    return ans
};