LeetCode 1675. 数组的最小偏移量（堆+贪心）

本文主要是介绍LeetCode 1675. 数组的最小偏移量（堆+贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路：

先将所有数变成偶数，这样所有数都只能除以二操作了。
所有数放入大根堆中，每次将最大的数除以二，然后算出当前最小值最大值的差值。

class Solution {
public:int minimumDeviation(vector<int>& nums) {int n = nums.size();priority_queue<int>Q;int mi = 1e9,ans = 1e9;for(int i = 0;i < n;i++) {if(nums[i] & 1) nums[i] <<= 1;Q.push(nums[i]);mi = min(mi,nums[i]);}while(!Q.empty()) {int now = Q.top();Q.pop();ans = min(ans,now - mi);if(now & 1) break; //最大值改变不了了mi = min(mi,now / 2);Q.push(now / 2);}return ans;}
};