LeetCode 1675. 数组的最小偏移量

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 贪心 堆（优先队列） 有序集合

题目描述

✅ 1675. 数组的最小偏移量

image-20260929090826494

image-20260929090826602

题意分析

数组元素都是正整数，每次可以把偶数除以 2，或把奇数乘以 2，次数不限。每个元素可以独立操作，要求最终数组的最大值减最小值尽可能小。

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

核心思路

[!blue]
先把每个元素放到所有可达值的最大端，再统一向下搜索。 原本为奇数的元素只能在自身和两倍之间切换，因此先将它翻倍；原本为偶数的元素保留原值，之后可连续除以 2，直到变成奇数。到了奇数再翻倍只会回到链上的前一个值，不会产生更大的新候选，所以这些下降链已经包含全部可达值。

用最大堆各保存每个元素的一个当前候选，另用 minimum 保存当前最小值。每轮先计算 maximum-minimum，再尝试把最大值减半。只降低其他元素不会降低当前最大值，却可能使最小值更小，因此当前状态若要改善，必须先处理最大值。

这也不会漏掉需要组合多次操作的最优解。固定任意可行方案的最大值 M，堆算法会逐一降低所有超过 M 的值，直到每个元素都取到“不超过 M 的最大可达值”。这些取值不会低于该方案对应的元素，所以最小值不会更低，最大值又不超过 M，得到的极差不会比该方案更差。

最大值为奇数时，它已经到达自己可达链的最低点，无法再缩小；继续降低其他元素只能使极差不变或变大，可以结束。必须先结算这一轮的极差，再判断退出。每次减半后用 minimum = min(minimum, reduced) 更新最小值，因为新值可能成为新的下界。

解题步骤

  1. 把奇数翻倍、偶数保持原值，全部加入最大堆，同时计算 minimum。
  2. 取出 maximum，用当前极差更新历史最优答案。
  3. 若 maximum 为奇数，返回已经更新的答案。
  4. 否则将它减半，更新 minimum 并重新入堆，继续下一轮。

每条正整数下降链都是有限的，最终一定会遇到无法继续下降的奇数最大值。堆保留重复元素，因为相同数值也代表不同数组位置；每轮只修改被取出的那一个元素。题目原值最多为 10^9，归一化后最多为 2×10^9，代码中的整数类型可以保存。

代码实现

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+1)\log(V+1))$，$V$ 为归一化后的最大值。每个元素最多减半 $O(\log(V+1))$ 次，每次出入堆耗时 $O(\log(n+1))$。
  • 空间复杂度：$O(n)$，保存当前值。

关键点总结

[!green]

  • 归一化确定完整可达范围，不是允许任意偶数翻倍。
  • 候选极差在当前最大值被改变前计算。
  • 最小值只会不变或降低，减半后及时更新。

易错点总结

[!yellow]

  • 不先归一化奇数：漏掉通过翻倍改善极差的方案。
  • 奇数最大值继续除二：产生不可达的值。
  • 最小值不更新：可能算出不属于真实配置的极差。
  • 遇到奇数先退出再更新答案：可能漏掉最后的最优状态。

相似题目

题目 难度 关联与区别
632. 最小区间 困难 每个数的可达值形成一组候选，选择各组一个值最小化范围，与最小覆盖区间模型相同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/62332598
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！