LeetCode 1675. 数组的最小偏移量

2021-06-01 HGNULB 约 12 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1675. 数组的最小偏移量

题意分析

数组里的每个数可以反复做两种操作：偶数可以除以 2，奇数可以乘以 2。偏移量定义为数组中最大值与最小值之差，要求把偏移量降到最小。

先把「一个数能变成哪些值」这件事想清楚。奇数 x 只能乘 2 变成 2x，而 2x 是偶数、可以再除回 x，除完又是奇数、乘 2 又回到 2x——所以奇数的可达集合只有 {x, 2x} 两个值。偶数 x 可以不断除 2，直到出现奇数为止，比如 12 能到 12、6、3；而 3 是奇数还能乘 2 回到 6，绕不出这条链。

于是每个数的可达集合都是一条有限的链：把它一路除到奇数得到 odd，链就是 odd, 2·odd, 4·odd, … 直到不超过原始值的两倍那一项。链的上端是「原值若为奇数则乘 2，若为偶数则保持原值」，链的下端是那个奇数。链长不超过 $\log$ 级别。

更关键的是方向的不对称：只要先把所有数都推到各自链的顶端（奇数乘 2、偶数不动），此后所有数就只能沿链往下走，不可能再上去。这一步预处理把「双向可调」变成了「单向递减」，是全题的转折点。

目标是最小化最大值与最小值之差。既然所有数只能下降，最大值就只能下降、最小值也只能下降。要缩小差距，唯一能做的就是压低当前的最大值——抬高最小值是做不到的。

数据规模是 $n \le 5 \times 10^4$，元素值不超过 $10^9$。乘 2 后上限是 $2 \times 10^9$，超过 32 位有符号整数的一半，要留意类型选择。链长约 31，所以总的下降步数在 $n \log V$ 量级。

边界包括：所有数已经相等（答案 0）；数组只有一个元素（答案 0）；以及最大值本身已经是奇数、无法再降。

解法：最大堆逐步缩小最大值

核心思路

暴力做法是枚举每个数在自己链上停在哪一层，$O(31^n)$ 级别，完全不可行。即使改成「枚举最终最小值，再让每个数取不小于它的最小可达值」，也需要对每个候选最小值扫一遍全部元素，候选量级是 $n \log V$，总复杂度 $O(n^2 \log V)$，在 $5 \times 10^4$ 下依然吃力。

瓶颈在于把两个方向的调整搅在了一起。把所有奇数先乘 2 之后，操作被规约成单向的「谁太大就把谁减半」，决策空间立刻塌缩。

关键观察：在只能下降的世界里，当前的最小值是不可能被抬高的，所以此刻的偏移量下界就是「当前最大值减当前最小值」。要想让答案更小，唯一有意义的动作是把当前最大值减半——对任何非最大元素动手，都不会改变最大值，也不会让最小值变大，纯属浪费。

于是流程变成：把所有数推到链顶放进大顶堆，同时记录当前最小值；反复取出堆顶（当前最大值），用「堆顶减最小值」更新答案，然后把堆顶减半再放回，并用这个新值刷新最小值。

不变量是：堆中始终是全体元素当前的取值，minVal 始终是它们的最小值，answer 始终是至今见过的所有合法状态中的最小偏移量。每轮取出的堆顶就是当前最大值，因此每轮计算出的差值都对应一个真实可达的数组状态，答案不会算出无法达到的值。

终止条件是堆顶为奇数。奇数已经在自己链的底端，不能再降；而它又是当前的最大值，意味着最大值再也无法下降，后续所有状态的偏移量都不会更小，可以立即停止。注意必须先用它更新答案再判断退出，因为它本身也构成一个合法状态。

为什么贪心是最优的？设某个最优配置的最大值为 $M$。$M$ 必是某条链上的可达值，算法迟早会处理到“当前最大值为 $M$”的状态；在此之前，它只会减半大于 $M$ 的元素。此时每个元素都停在自己链上不超过 $M$ 的最大可达值，因此其最小值不会小于最优配置的最小值，当前偏移量也就不会大于最优值。算法枚举并取了这些真实状态的最小偏移量，所以必然得到全局最优。

解题步骤

归一化到链顶：遍历数组，奇数乘 2，偶数保持原样，把结果压入大顶堆，同时用一个变量记录这些值中的最小者。这一步之后所有元素只能下降，是整个算法成立的前提；若不做这一步，某些奇数还留有「向上」的余地，堆顶未必是全局最优路径上的最大值。

用归一化后的堆顶与最小值初始化答案。这个初始状态本身就是一个合法数组配置，必须计入候选，漏掉它会在「初始状态就是最优」的用例上出错。

循环取出堆顶。堆顶即当前最大值，取出后先用「堆顶减 minVal」尝试更新答案——这一步要在任何修改之前做，因为它刻画的是当前这一瞬间的真实偏移量。

若堆顶是奇数就退出循环。奇数已在链底，最大值无法再降，继续操作只会让其他元素变小、最小值变小，差距只会更大或持平。退出前答案已经更新过，不会漏解。

否则把堆顶减半，用新值刷新 minVal，再压回堆中。刷新最小值必须在压回之前或之后立刻完成，因为减半后的值可能成为新的全局最小者；漏掉这一步会让 minVal 停留在过期值上，后续差值全部算大。

返回答案。

以 nums = [1, 2, 3, 4] 走一遍，预期答案 1。

归一化：1 是奇数变成 2，2 是偶数保持 2，3 是奇数变成 6，4 是偶数保持 4。堆中是 {2, 2, 6, 4}，minVal = 2。初始答案 $6 - 2 = 4$。

第一轮取出 6：$6 - 2 = 4$ 不小于当前答案 4，不更新；6 是偶数，减半得 3，3 不小于 minVal = 2 所以最小值不变，压回堆得 {2, 2, 4, 3}。第二轮取出 4：$4 - 2 = 2 < 4$，答案更新为 2；4 是偶数，减半得 2，压回堆得 {2, 2, 3, 2}，minVal 仍是 2。第三轮取出 3：$3 - 2 = 1 < 2$，答案更新为 1；3 是奇数，退出循环。

返回 1，对应数组状态 {2, 2, 3, 2} 的最大值 3 与最小值 2 之差，确实是最优。

本例里 minVal 始终没有变化，看不出刷新最小值的必要性，换个用例就很明显。取 nums = [8, 10]：归一化后堆是 {8, 10}、minVal = 8、初始答案 2。取出 10，$10 - 8 = 2$ 不更新；10 是偶数减半得 5，5 小于 8，minVal 刷新为 5，堆变成 {8, 5}。取出 8，$8 - 5 = 3$ 不更新；减半得 4，minVal 刷新为 4，堆变成 {5, 4}。取出 5，$5 - 4 = 1$，答案更新为 1；5 是奇数，退出。答案 1，对应 8 降到 4、10 降到 5 的配置。若不刷新 minVal，第二轮会算出 $8 - 8 = 0$ 并把答案错误地压到 0——一个根本不存在的配置。

代码实现

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        int minimum = Integer.MAX_VALUE;

        for (int value : nums) {
            int normalized = (value & 1) == 1 ? value * 2 : value;
            heap.offer(normalized);
            minimum = Math.min(minimum, normalized);
        }

        int answer = heap.peek() - minimum;
        while (true) {
            int maximum = heap.poll();
            answer = Math.min(answer, maximum - minimum);
            if ((maximum & 1) == 1) {
                return answer;
            }

            int reduced = maximum / 2;
            minimum = Math.min(minimum, reduced);
            heap.offer(reduced);
        }
    }
}

import "container/heap"

type maxHeap []int

func (h maxHeap) Len() int           { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *maxHeap) Push(value interface{}) {
	*h = append(*h, value.(int))
}

func (h *maxHeap) Pop() interface{} {
	old := *h
	last := old[len(old)-1]
	*h = old[:len(old)-1]
	return last
}

func minimumDeviation(nums []int) int {
	pq := &maxHeap{}
	minimum := int(^uint(0) >> 1)

	for _, value := range nums {
		normalized := value
		if value&1 == 1 {
			normalized *= 2
		}
		heap.Push(pq, normalized)
		if normalized < minimum {
			minimum = normalized
		}
	}

	answer := (*pq)[0] - minimum
	for {
		maximum := heap.Pop(pq).(int)
		if maximum-minimum < answer {
			answer = maximum - minimum
		}
		if maximum&1 == 1 {
			return answer
		}

		reduced := maximum / 2
		if reduced < minimum {
			minimum = reduced
		}
		heap.Push(pq, reduced)
	}
}

复杂度分析

时间复杂度：$O(n \log n \log V)$，其中 $n$ 是元素个数、$V$ 是元素最大值。建堆是 $O(n \log n)$；此后每个元素沿自己的链最多下降 $O(\log V)$ 次，总下降次数上界是 $O(n \log V)$，每次伴随一次弹出与一次插入，各 $O(\log n)$。本题 $n \le 5 \times 10^4$、$\log V \approx 31$，实际运行远低于这个上界，因为一旦堆顶变成奇数就立刻终止。

空间复杂度：$O(n)$，堆中始终保存全部 n 个元素的当前取值。除此之外只有 answer 与 minVal 两个标量。

关键点总结

先把「双向可调」规约成「单向可调」，是这道题从困难变中等的关键一步。遇到操作可逆的题，优先寻找一个能把所有元素推到极端的预处理，让后续决策只剩一个方向。

「只能下降」的世界里最小值不可能变大，所以缩小极差的唯一手段是压低最大值。把可行动作从「随便选一个数操作」缩到「只操作最大值」，贪心的正确性就摆在明面上。

每一轮都要先结算再操作：取出堆顶后立刻用它更新答案，因为这一瞬间的堆状态对应一个真实可达的数组配置，改完再算就把这个状态跳过去了。

终止条件是「当前最大值已在链底」，不是「堆空」也不是「达到某个次数」。能说清「为什么此时可以停」是这题的核心考点。

维护最小值要与堆的每次变更同步。堆本身只提供最大值，最小值必须自己在每次下降时刷新，否则差值全部算错——这是「用堆维护一端、用变量维护另一端」这一模式的固定配套动作。

面试视角：先分析每个数的可达集合是一条链，再指出归一化到链顶后操作变单向，然后给出「只压最大值」的贪心与大顶堆实现，最后讲终止条件。面试官常追问「能不能用有序集合替代」，答案是可以，TreeSet 或 multiset 能同时拿到两端、省掉手工维护最小值，复杂度相同；再追问「为什么不能用二分答案」，回答是可行性判定需要为每个元素在链上选层，判定本身就不比原问题简单。

易错点总结

错误写法：跳过归一化，直接把原数组放进大顶堆。用例 nums = [1, 2, 3, 4] → 堆顶是 4，减半得 2，接着 3 是奇数直接退出，答案算成 $3 - 1 = 2$；正确答案是 1，因为把 1 乘 2、把 3 乘 2 后才存在更优状态。

错误写法：归一化时用原值而不是乘 2 后的值来记录 minVal。用例 nums = [1, 2] → minVal 记成 1，但堆里实际是 {2, 2}，第一轮算出 $2 - 1 = 1$，正确答案是 0。

错误写法：不判奇偶，取出堆顶就无条件减半再压回。用例 nums = [3, 4] → 归一化后 {6, 4}，正常流程答案是 1；错误写法把 3 也除成 1（整数除法），堆里出现了根本不可达的值，最终返回 0。

错误写法：减半之后忘记刷新 minVal。用例 nums = [8, 10] → 归一化后 {8, 10}、minVal = 8；10 减半成 5 后最小值应变为 5，漏刷新则下一轮算出 $8 - 8 = 0$，返回 0，正确答案是 1。

错误写法：判断到堆顶是奇数就直接退出，退出前不更新答案。用例 nums = [4, 1, 5, 20, 3] → 最后取出的 5 恰好给出最优差值 3，先退出就把它丢了，答案停在 4。

错误写法：终止条件写成「堆为空」而不判奇数。用例 nums = [3] → 6 减半为 3，3 是奇数但仍被压回堆中，下一轮又取出 3、又压回，程序陷入死循环。

错误写法：用小顶堆维护最小值、每轮抬高最小值。用例 nums = [1, 2, 3, 4] → 归一化后所有数只能下降，抬高最小值的操作根本不存在，算法在第一轮就无路可走，返回初始值 4，正确答案是 1。

错误写法：比较器写成 (a, b) -> a - b。用例 nums = [1, 2, 3, 4] → 变成小顶堆，每轮取出的是最小值而非最大值，answer 的更新基于错误的一端，返回值与正确答案 1 无关。

错误写法：用 x * 2 时用 32 位类型且未评估上界。用例 nums 含 $10^9$ 附近的奇数 → 乘 2 得 $2 \times 10^9$，虽仍在 int 范围内，但若中间再做一次乘 2 或与其他值相加就会溢出为负，堆序完全错乱。

错误写法：把答案算成「归一化后最大值减归一化后最小值」直接返回。用例 nums = [1, 2, 3, 4] → 返回 4，正确答案是 1；归一化只是起点，真正的优化发生在后续的逐步下降过程中。

相似题目

题目	难度	考察点
1046. 最后一块石头的重量	简单	大顶堆模拟的最简形态，每轮取两个最大值合并，无需归一化也无终止条件推导
215. 数组中的第K个最大元素	中等	堆只用于选取而不参与状态演化，重点是大小为 K 的堆与快速选择的取舍
295. 数据流的中位数	困难	用两个堆同时把住两端，正是本题「堆管一端、变量管另一端」的通用化版本
632. 最小区间	困难	同样是「堆顶给最大值、变量记最小值、每轮推进最小的那个」，结构几乎一一对应
1648. 销售价值减少的颜色球	中等	同样有「反复削最大值」的直觉，但操作次数达 $10^9$，必须改用二分批量结算
2462. 雇佣 K 位工人的总代价	中等	候选来自双端窗口，需要两个堆配合指针推进，考察堆与滑动窗口的结合
910. 最小差值 II	中等	同样求最小极差，但每个数只能加或减固定值一次，排序后枚举分界点即可
1438. 绝对差不超过限制的最长连续子数组	中等	极差作为约束而非目标，需要单调队列在滑动窗口内同时维护最大值与最小值