What is the main strategy to solve Minimize Deviation in Array?

The key strategy is to normalize numbers to their minimum even forms and then repeatedly halve the maximum using a max-heap, ensuring the deviation decreases optimally.

Why do we use a max-heap instead of a min-heap?

A max-heap efficiently tracks the current largest number, which is the primary contributor to deviation, allowing the greedy halving operation to reduce deviation correctly.

How do odd and even numbers differ in allowed operations?

Odd numbers can only be multiplied by 2 once to become even, while even numbers can be repeatedly halved until they turn odd. This invariant drives the solution's correctness.

What is the time complexity of this approach?

Time complexity is O(n log n * log(maxNum)) because each element can be pushed and popped from the heap multiple times proportional to the number of times it can be halved.

Can this approach handle large arrays up to 5*10^4 elements?

Yes, by using a heap and the greedy halving strategy, it efficiently reduces deviation without sorting the entire array multiple times, scaling to the problem's constraints.

#1675

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

数组的最小偏移量

给你一个由 n 个正整数组成的数组 nums 。你可以对数组的任意元素执行任意次数的两类操作：如果元素是偶数，除以 2 例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3, 2 ] 如果元素是奇数，乘上 2 例如，如果数组是 [1,2,…

数组贪心堆（优先队列）有序集合

题目描述

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

lightbulb

解题思路

方法一：贪心 + 优先队列

直观上，为了得到数组的最小偏移量，我们需要将减小数组的最大值，增大数组的最小值。

由于每次可以执行乘、除两种操作：将奇数乘以 $2$ ；将偶数除以 $2$ ，情况较为复杂，我们可以将奇数统一乘以 $2$ ，转成偶数，这样就等价于只有一种除法操作。除法操作只能减少某个数，而只有减少最大值，结果才可能更优。

因此，我们用优先队列（大根堆）维护数组的最大值，每次取出堆顶元素做除法操作，将新值放入堆中，并且更新最小值以及堆顶元素与最小值的差值的最小值。

当堆顶元素为奇数时，操作停止。

时间复杂度 $O(n\log n \times \log m)$ 。其中 $n$ , $m$ 分别是数组 nums 的长度以及数组的最大元素。由于数组中的最大元素除以 $2$ 的操作最多有 $O(\log m)$ 次，因此全部元素除以 $2$ 的操作最多有 $O(n\log m)$ 次。每次弹出、放入堆的操作，时间复杂度为 $O(\log n)$ 。因此，总的时间复杂度为 $O(n\log n \times \log m)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        h = []
        mi = inf
        for v in nums:
            if v & 1:
                v <<= 1
            h.append(-v)
            mi = min(mi, v)
        heapify(h)
        ans = -h[0] - mi
        while h[0] % 2 == 0:
            x = heappop(h) // 2
            heappush(h, x)
            mi = min(mi, -x)
            ans = min(ans, -h[0] - mi)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to heap operations performed for each element at most log(max(nums)) times. Space complexity is O(n) for storing the heap and tracking the minimum element.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates who attempt naive sorting without heap will likely hit timeouts.
question_mark
Look for recognition that the greedy approach must focus on the maximum element while preserving array invariants.
question_mark
Ensure they understand why odd numbers are only multiplied once and even numbers can be repeatedly halved.

warning

常见陷阱

外企场景

error
Failing to normalize odd numbers initially, causing incorrect deviation calculation.
error
Using a min-heap instead of a max-heap, which reverses the greedy strategy.
error
Not updating the current minimum when halving the maximum, leading to wrong deviation results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize deviation with additional constraint on number of operations allowed.
arrow_right_alt
Find maximum deviation instead of minimum after allowed operations.
arrow_right_alt
Solve for arrays containing zeros and ones with same doubling/halving rules.

help

常见问题

外企场景

继续练习

#1606 找到处理最多请求的服务器 #1686 石子游戏 VI #1648 销售价值减少的颜色球