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

[TOC]

## Description
**example**

## Ideas
* 首先先觀察：奇數只能越變越大(`odd *= 2`)，偶數只會越變越小(`even /= 2`)
* 所以nums首先要先排序，只需要判斷最大值及最小值改變之後會落在哪個區間
* 而只有改變後的數字落在原先區間之間答案才會變小

* tricky的地方就來了，我先假設全部數字都變成最小值(全部都是奇數)

    for i in range(len(nums)):
        while nums[i] % 2:
            nums[i] <<= 1

* 然後儲存到max-heap裡面，每一次的動作如下
step 1: curr_max = hp.pop()
step 2: res = min(res, curr_max - golbal_min)
step 3: 若curr_max是偶數->
* 表示還能將它除以2，接著push回heap當中，並維持global_min，返回step 1
* 否則return res
### way1
python 3

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        # python有sortedlist這個外掛
        # 當然也可以用heapq
        from sortedcontainers import SortedList
        
        for i in range(len(nums)):
            while nums[i] % 2:
                nums[i] <<= 1
        
        sl = SortedList(nums)
        
        res = sl[-1] - sl[0]
        
        while sl:
            
            n = sl.pop()
            res = min(res, n - sl[0])
            if n % 2:
                break
            else:
                sl.add(n // 2)
        
        return res

* 發現當我們將數字都變成最小值時，有些步驟就顯得多餘，例如:

input: nums = [2**32, 2**32 - 1]
初始化的heap = [1, 2**32 - 1]

* 所以改成將數字全部變成最大值(even)
### way2
python 3

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        from sortedcontainers import SortedList
        sl = []
        for i in range(len(nums)):
            if nums[i] % 2:
                sl.append(nums[i] * 2)
            else:
                sl.append(nums[i])
        
        sl = SortedList(sl)
        res = sl[-1] - sl[0]
        while sl:
            curr = sl.pop()
            res = min(res, curr - sl[0])
            
            if curr % 2:
                break
            else:
                sl.add(curr // 2)
        
        return res

C++

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int mini = INT_MAX;
        priority_queue<int> pq;
        for(auto n: nums) {
            if (n % 2) {
                pq.push(n * 2);
                mini = min(mini, n * 2);
            } else {
                pq.push(n);
                mini = min(mini, n);
            }
        }
        
        int res = INT_MAX;
        while (!pq.empty()) {
            int curr = pq.top();
            pq.pop();
            res = min(res, curr - mini);
            
            if (curr % 2) {
                break;
            } else {
                pq.push(curr / 2);
                mini = min(curr / 2, mini);
            }
        }
        return res;
    }
};