LEETCODE 1675. Minimize Deviation in Array 解题思路分析

题目大意：

数组的最小偏移量

给你一个由 n 个正整数组成的数组 nums 。

你可以对数组的任意元素执行任意次数的两类操作：

如果元素是 偶数 ，除以 2
例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
如果元素是 奇数 ，乘上 2
例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

示例 1：

输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1

示例 2：

输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3

示例 3：

输入：nums = [2,10,8]
输出：3

提示：

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1675

解题思路分析：

这些日子一直在忙项目，刷题的时间越来越少，感觉状态大不如前，总结一点就是，如果你打算去大厂面试，面试前一周甚至两周时间一定要坚持练习保持状态才可以。

言归正传，回到本题，题目要求求出偏差值(数组中最大值与最小值之差)最小的可能性，如果想让偏差值最小，那么我们需要不断地扩大数组中最小值，以及不断缩小最大值，直到最大值不能再缩小并且最小值不能再扩大为止，当前的偏差值即是最小情况。道理都懂，但实际操作起来确很麻烦，因为某个数字不断地变大再变小会使得情况变得非常复杂。所以我们应尽量将问题简单化。

对于本题，只有奇数可以扩大（乘2），但只限1次（因为扩大后会变成偶数），而偶数可以缩小1至n次，直到变为奇数为止。解题时，我们可以将所有奇数先变为偶数，即数组中的数字全部是偶数，这样一来，有两个好处：

1. 我们只考虑减小某个数字即可。
2. 每一次只考虑减小最大的偶数即可。（减小其他偶数并不会使得偏差值变得更小）

接下来思路就清晰了，我们来总结一下解题步骤

1. 将数组中所有数字变成偶数，并使用PriorityQueue来存储所有偶数。
2. 取出PriorityQueue中最大的数字，如果是偶数，将其减半再放回PriorityQueue中。如果是奇数，那么代表最大值无法再继续缩小，因此当前值与PriorityQueue中最小值之差即是返回结果。
3. 通过步骤2不断更新PriorityQueue中数字，并维护数组中的最大值以及最小值，并通过最大值与最小值更新全局最小偏差值

实现代码：

public int minimumDeviation(int[] nums) {
    // 使用PriorityQueue由大到小排序数组中的数字
    PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
    // 最大值与最小值
    int max=0,min=Integer.MAX_VALUE;
    // 将数组中所有数字先变为偶数
    for(int n : nums){ // 循环每个数字
        if(n%2==1) n*=2; // 如果是奇数，先变为偶数
        if(n<min) min=n; // 更新最小值
        if(n>max) max=n; // 更新最大值
        q.offer(n);
    }
    int res = max - min; // 返回结果（最小偏差值）
    while(q.size()>0){
        int n = q.poll(); // 取出PriorityQueue中的最大值
        // 如果最大值为奇数，代表最大值无法再减小，退出
        if(n % 2 == 1) break;
        n /= 2; // 将当前数字除以2
        q.offer(n); // 将当前数字放回PriorityQueue中
        min=Math.min(min,n); // 用当前数字更新最小值
        max=q.peek(); // 用PriorityQueue中首元素更新最大值
        res = Math.min(res, max - min); // 更新最小偏差值
    }
    return res;
}

本题解法执行时间为80ms。

Runtime: 80 ms, faster than 77.85% of Java online submissions for Minimize Deviation in Array.

Memory Usage: 55 MB, less than 53.87% of Java online submissions for Minimize Deviation in Array.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1675-minimize-deviation-in-array-解题思路分析/