1675. Minimize Deviation in Array (pq or TreeSet

use PriorityQueue

T: O(n * logn* logM); M is the largest number, n is length of nums , => logM is max 32 (32-bit int), which is treated as constant => so O(nlogn) is fine

S: O(m)

class Solution {
    public int minimumDeviation(int[] nums) {
        Queue<Integer> pq = new PriorityQueue<>();
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 1) {
                num = 2*num;
            }
            pq.offer(-num);
            min = Math.min(min, num);
        }
        int res = Integer.MAX_VALUE;
        while (true) {
            int largget = -pq.poll();
            res = Math.min(res, largget - min);
            
            if (largget % 2 == 0) {
                min = Math.min(min, largget/2);
                pq.offer(-largget/2);
            } else {
                break;
            }
        }
        return res;
    }
}

/*
make max diff(deviation) minimized
*/

use TreeSet

T: O(n * logn* logM); M is the largest number, n is length of nums , => logM is max 32 (32-bit int), which is treated as constant => so O(nlogn) is fine

S: O(m)

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                set.add(num);
            } else {
                set.add(num*2);
            }
        }
        int res = Integer.MAX_VALUE;
        while (true) {
            int largget = set.last();
            res = Math.min(res, largget - set.first());
            
            if (largget % 2 == 0) {
                set.remove(largget);
                set.add(largget/2);
            } else {
                break;
            }
        }
        return res;
    }
}

/*
make max diff(deviation) minimized
*/