Hard

题目描述

给你一个由 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 <= 5 * 10^4
  • 1 <= nums[i] <= 10^9

解题思路

这是一个经典的贪心+优先队列问题。关键观察是：

核心思路：

  1. 奇数只能变大（乘2），偶数只能变小（除2）
  2. 为了最小化偏差，我们希望缩小最大值和最小值的差距
  3. 策略：先将所有奇数变为它们能达到的最大值（乘2变偶数），然后只能通过减少最大值来缩小偏差

算法步骤：

  1. 预处理：将所有奇数乘2变为偶数，这样后续只需要考虑除2操作
  2. 使用大顶堆维护当前所有数值，同时记录最小值
  3. 每次取出最大值：
    • 如果是奇数，无法继续减小，算法结束
    • 如果是偶数，将其除2后重新加入堆
    • 更新最小值和当前偏差的最小值
  4. 当堆顶变为奇数时，所有数都无法继续减小，返回答案

这个方法保证了我们尝试所有可能的数组状态，因为每个偶数都会被不断除2直到变为奇数。

时间复杂度： O(n log n log M)，其中M是数组中的最大值
空间复杂度： O(n)

代码实现

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> pq;
        int minVal = INT_MAX;
        
        // 将所有奇数变为偶数，并找到最小值
        for (int num : nums) {
            if (num % 2 == 1) {
                num *= 2;
            }
            pq.push(num);
            minVal = min(minVal, num);
        }
        
        int minDeviation = pq.top() - minVal;
        
        // 不断缩小最大值
        while (pq.top() % 2 == 0) {
            int maxVal = pq.top();
            pq.pop();
            maxVal /= 2;
            minVal = min(minVal, maxVal);
            pq.push(maxVal);
            minDeviation = min(minDeviation, pq.top() - minVal);
        }
        
        return minDeviation;
    }
};

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        import heapq
        
        # Python的heapq是最小堆，所以用负数模拟最大堆
        max_heap = []
        min_val = float('inf')
        
        # 将所有奇数变为偶数，并找到最小值
        for num in nums:
            if num % 2 == 1:
                num *= 2
            heapq.heappush(max_heap, -num)
            min_val = min(min_val, num)
        
        min_deviation = -max_heap[0] - min_val
        
        # 不断缩小最大值
        while -max_heap[0] % 2 == 0:
            max_val = -heapq.heappop(max_heap)
            max_val //= 2
            min_val = min(min_val, max_val)
            heapq.heappush(max_heap, -max_val)
            min_deviation = min(min_deviation, -max_heap[0] - min_val)
        
        return min_deviation

public class Solution {
    public int MinimumDeviation(int[] nums) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        int minVal = int.MaxValue;
        
        // 将所有奇数变为偶数，并找到最小值
        foreach (int num in nums) {
            int val = num;
            if (val % 2 == 1) {
                val *= 2;
            }
            pq.Enqueue(val, val);
            minVal = Math.Min(minVal, val);
        }
        
        int minDeviation = pq.Peek() - minVal;
        
        // 不断缩小最大值
        while (pq.Peek() % 2 == 0) {
            int maxVal = pq.Dequeue();
            maxVal /= 2;
            minVal = Math.Min(minVal, maxVal);
            pq.Enqueue(maxVal, maxVal);
            minDeviation = Math.Min(minDeviation, pq.Peek() - minVal);
        }
        
        return minDeviation;
    }
}

var minimumDeviation = function(nums) {
    const maxHeap = new MaxPriorityQueue();
    let min = Infinity;
    
    for (let num of nums) {
        if (num % 2 === 1) {
            num *= 2;
        }
        maxHeap.enqueue(num);
        min = Math.min(min, num);
    }
    
    let result = maxHeap.front().element - min;
    
    while (maxHeap.front().element % 2 === 0) {
        const max = maxHeap.dequeue().element;
        const newVal = max / 2;
        maxHeap.enqueue(newVal);
        min = Math.min(min, newVal);
        result = Math.min(result, maxHeap.front().element - min);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法说明
时间复杂度O(n log n log M)n是数组长度，M是数组最大值。每个数最多被除log M次，每次堆操作O(log n)
空间复杂度O(n)优先队列存储n个元素