1675.Minimize Deviation in Array
===

###### tags: `Hard`,`Array`,`Greedy`,`Heap`

[1675. Minimize Deviation in Array](https://leetcode.com/problems/minimize-deviation-in-array/)

### 題目描述

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` <= 5 * 10^4^
* 1 <= `nums[i]` <= 10^9^

### 解答

#### C++
##### 思路:
1. 奇數只能*2, 偶數只能/2, 找經過操作後最小的deviation
2. 因為奇數做*2後, 必定成為偶數且接下來只能/2, 故可以把當前奇數都*2後, 以當前數列全為偶數做思考
3. 根據題目我們其實也只關心最大跟最小值的差值, 所以可以紀錄最小值後, 開始把最大值提出來/2, 看不可以縮小差距, 可以的話持續迭代, 直到最大值是奇數不能再/2結束

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int min_v = INT_MAX, res = INT_MAX;
        priority_queue<int> q;
        for(int i = 0; i < nums.size(); i++)
        {
            nums[i] = nums[i]&1 ? nums[i]*2 : nums[i];
            min_v = min(min_v, nums[i]);
            q.push(nums[i]);
        }
        
        res = q.top() - min_v;
        while(q.top() % 2 == 0)
        {
            int v = q.top()/2; q.pop();
            q.push(v);
            min_v = min(min_v, v);
            res = min(res, q.top()-min_v);
        }
        return res;
    }
};

Time: $O(nlog(n))$ 最多做`n`次, 每次push一個值進priority queue
Extra Space: $O(n)$

> [name=XD] [time= Feb 24, 2023]

##### 方法1
跟天宇一樣，但考慮到數字是$2^d$的倍數的話，那時間複雜度其實是$O(nd\log n)$
Runtime 602ms (Beats 38.66%)

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int lower = INT_MAX;
        priority_queue<int> pq;
        for (int i = 0; i < nums.size(); i++) {
            nums[i] <<= nums[i] & 1;
            lower = min(lower, nums[i]);
            pq.push(nums[i]);
        }
        int ans = pq.top() - lower;
        while (pq.top() % 2 == 0) {
            int value = pq.top() / 2;
            pq.pop();
            pq.push(value);
            lower = min(lower, value);
            ans = min(ans, pq.top() - lower);
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sat, Feb 25, 2023]

##### 方法2
利用set來減少相同的數字重複檢查，複雜度一樣是$O(nd\log n)$，但執行時間能減少接近一半
Runtime 333ms (Beats 89.8%)

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int lower = INT_MAX;
        set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            nums[i] <<= nums[i] & 1;
            lower = min(lower, nums[i]);
            s.insert(nums[i]);
        }
        int ans = *s.rbegin() - lower;
        while (*s.rbegin() % 2 == 0) {
            int value = *s.rbegin();
            s.erase(value);
            value = value / 2;
            s.insert(value);
            lower = min(lower, value);
            ans = min(ans, *s.rbegin() - lower);
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sat, Feb 25, 2023]

##### 方法3
- 思路
1. 從前面的方法中會發現，將每個數字一直除以2之後，最終會停在最大的奇數(max_odd)上。
2. 那試想一下，最小的deviation發生時，這個數列是否會包含這個max_odd呢？答案是肯定的。證明也很簡單，在不失一般性的情況下，我們先假設max_odd還未出現，仍是$2\times$max_odd，我們可以將數列中$\geq 2 \times$max_odd的所有數字都除以2，這樣整個數列的range就會縮小了，而且此時數列中就會包含max_odd。
3. 接下來就是想辦法讓數列中的數字盡量維持在max_odd附近就好。
4. 再加一個小技巧，除以2這個運算需要考慮到一個數字是不是偶數，但如果我們把所有的偶數都先除以2一次，這個在max_odd附近的數列，無論奇偶數都只需要考慮乘2就好。
- 作法
1. 找出每個數字除2到變為奇數後，找出最大的奇數出來。
2. 對原始的數列中的數字，奇數不動，偶數的一律都先除以2一次，之後再持續除到不大於max_odd。然後將這個數列排序。
3. 如圖，嘗試把從前面開始的一段數列乘以2，找出紅線範圍最小的情況。
Time: $O(nd + n\log n)$
Space: $O(1)$

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int max_odd = 1;
        for (auto num : nums) {
            while (num % 2 == 0) num >>= 1;
            max_odd = max(max_odd, num);
        }
        for (auto& num : nums) {
            if (num % 2 == 0) {
                num >>= 1;
                while (num > max_odd) num >>= 1;
            }
        }
        sort(nums.begin(), nums.end());
        int ans = max_odd - nums[0], n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            ans = min(ans, max(max_odd, nums[i] * 2) - min(nums[i+1], nums[0] * 2));
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sat, Feb 25, 2023]

#### Javascript

function minimumDeviation(nums) {
  const maxHeap = new MaxHeap();
  let min = Infinity;
  for (const num of nums) {
    if (num % 2 === 1) {
      maxHeap.push(num * 2);
      min = Math.min(min, num * 2);
    } else {
      maxHeap.push(num);
      min = Math.min(min, num);
    }
  }

  let result = maxHeap.top() - min;
  while (maxHeap.top() % 2 === 0) {
    const max = maxHeap.pop();
    min = Math.min(min, max / 2);
    maxHeap.push(max / 2);
    result = Math.min(result, maxHeap.top() - min);
  }

  return result;
}

// Priority Queue
class MaxHeap {
  constructor() {
    this.queue = [];
  }

  push(val) {
    this.queue.push(val);
    this.bubbleUp();
    return this;
  }

  pop() {
    const val = this.queue[0];
    const last = this.queue.pop();
    if (this.queue.length > 0) {
      this.queue[0] = last;
      this.bubbleDown();
    }

    return val;
  }

  top() {
    return this.queue[0];
  }

  bubbleUp() {
    let index = this.queue.length - 1;
    let parentIndex = ~~((index - 1) / 2);
    while (this.queue[index] > this.queue[parentIndex]) {
      [this.queue[index], this.queue[parentIndex]] = [this.queue[parentIndex], this.queue[index]];
      index = parentIndex;
      parentIndex = ~~((index - 1) / 2);
    }

    return this;
  }

  bubbleDown() {
    let index = 0;
    let leftIndex = index * 2 + 1;
    let rightIndex = index * 2 + 2;
    let maxIndex = index;
    while (leftIndex < this.queue.length) {
      if (this.queue[leftIndex] > this.queue[maxIndex]) {
        maxIndex = leftIndex;
      }
      if (rightIndex < this.queue.length && this.queue[rightIndex] > this.queue[maxIndex]) {
        maxIndex = rightIndex;
      }

      if (maxIndex === index) break;

      [this.queue[index], this.queue[maxIndex]] = [this.queue[maxIndex], this.queue[index]];
      index = maxIndex;
      leftIndex = index * 2 + 1;
      rightIndex = index * 2 + 2;
    }

    return this;
  }
}

> 參考樓上兩位大神的方法1，先寫個max heap練習一下，結果錯了好幾次...
> [name=Marsgoat][time=Mar 2, 2023]

### Reference

https://leetcode.com/problems/minimize-deviation-in-array/solutions/3224070/javascript-8-lines-greedy-no-pq-time-o-nlogn-space-o-1-100/
分享一下看到一些很神的做法

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)