leetcode 1675. 数组的最小偏移量

Problem: 1675. 数组的最小偏移量https://leetcode.com/problems/minimize-deviation-in-array/solutions/955262/c-intuitions-and-flip-by-votrubac-3bbe/不会挺难的看了其他人的答案问了豆包的这道题的难点是数字存在上限奇数*2变成偶数偶数只能除以2所以最大值就是偶数当一个数字变成偶数以后只能变小/2所以对所有奇数*2拿到每个数字的最大值以及最小值计算每种最大值和最小值的差值拿到最小值Codeclass Solution { public: int minimumDeviation(vectorint nums) { priority_queueint, vectorint, decltype(lessint()) pq; int mi 999999999; for(int i : nums) { if((i1)0) { pq.push(i); mi min(mi, i); } else { i i * 2; pq.push(i); mi min(mi, i); } } int mx, ret 999999999; while(pq.top()%2 0) { mx pq.top(); ret min(ret, (mx - mi)); mx mx / 2; mi min(mi, mx); pq.push(mx); pq.pop(); } ret min(pq.top() - mi, ret); return ret; } };先把核心结论放最前面操作规则回顾奇数只能 ×2变大不能÷2偶数只能 ÷2变小不能×2很多人卡在这里为什么先把所有数扩到最大然后只不断缩小最大值就能找到最优解我们一层一层推导杜绝死记硬背。1. 先分析每个数字所有可达取值随便拿一个数看它能变成哪些数情况1奇数例如3允许操作只能先 ×2序列3 → 6 → 3 → 6 → …有效可选集合{3,6}最大值 6最小值 3情况2偶数例如8允许操作只能不断 ÷2序列8 →4 →2 →1有效可选集合{8,4,2,1}最大值 8最小值1✅重大发现任何数字 x它能达到的最大值是唯一固定的x 奇数max x*2x 偶数max x一旦到达这个最大值后续只能不断变小÷2再也不能变大不存在任何方式让数字超过这个上限。换句话所有数字能走到的区间[下限, 上限]上限固定不变。2. 为什么最优解一定出现在「全部数字都已经被扩大到上限」之后不断缩小最大值的过程里假设我们现在有一组数每个数都可以选区间内某个值a ∈ [ A m i n , A m a x ] , b ∈ [ B m i n , B m a x ] , c ∈ [ C m i n , C m a x ] a\in[A_{min},A_{max}],\;b\in[B_{min},B_{max}],\;c\in[C_{min},C_{max}]a∈[Amin​,Amax​],b∈[Bmin​,Bmax​],c∈[Cmin​,Cmax​]并且A m a x , B m a x , C m a x A_{max},B_{max},C_{max}Amax​,Bmax​,Cmax​是各自能到达的最大数值。我们目标从每个区间挑选一个数使得max(选中值) − min(选中值)最小。逆向思考能不能先全部拉到上限初始状态所有数字取最大值A m a x , B m a x , C m a x A_{max},B_{max},C_{max}Amax​,Bmax​,Cmax​此时当前全局最大值 堆顶全局最小值 所有上限里最小的那个。当前偏移量 最大值 - 最小值。现在唯一能优化偏移量的手段尝试降低全局最大值因为我们现在所有数字已经拉满上限任何数字不能再变大。想缩小【最大值−最小值】只有两条路把最大值变小唯一可行操作÷2把最小值变大 ❌【不可能所有数已经是最大值没法变大】 所以唯一可行的优化动作不断拿当前最大的数尝试÷2缩小。举个直观例子nums [1,2,3,4]各数上限1(奇数)→22→23→64→4初始集合[2,2,6,4]min_val 2堆大根堆6,4,2,2取出最大值6diff6-24。6是偶数可以/2 →3放回堆。更新min_val仍然2数组候选[2,2,3,4]当前最大值4diff4-22。4/2→2放回堆数组候选[2,2,3,2]当前最大值3diff3-21。3是奇数不能再除以2停止最小diff1正好是答案。3. 关键疑问会不会漏掉更优方案有人会问我能不能一开始不让某个数字扩到最大值直接选更小的值得到更好结果答案不会漏掉最优解严格证明思路假设存在一组最优选择方案S其中某个数字 x 没有选取它的最大值直接选了一个较小值。我们对比两条路径方案1算法路径x先拉满上限 → 再逐步÷2降到目标值方案2你设想x直接不取上限直接用小值这两条路径最终x可以到达完全一样的数值。算法流程就是模拟先拉满上限再一步步往下退。相当于遍历所有「逐步降低最大值」的合法局面。最优局面一定是其中某一步。反例演示帮你理解为什么不会漏假设存在一个最优解它要求最大值不是某个数的上限。那这个最大值一定是某个大数不断÷2之后得到的值这个局面一定会在我们循环「弹出最大值÷2放回」时被遍历到。4. 什么时候停止循环当堆顶当前最大值是奇数时停止。原因奇数不能÷2没法继续缩小全局最大值。既然最大值再也降不下去我们再也无法得到更小的差值可以直接结束。5. 总结极简逻辑链背诵版奇数最多只能扩大一次所有数字存在固定上限所有数字先拉到上限此时所有数字只能缩小、不能放大想要缩小【最大值−最小值】唯一手段不断把全局最大的数÷2每一次缩小后计算偏移量记录最小值如果最大值变成奇数无法继续缩小结束所有可行的候选局面全部遍历一定能找到最小偏移。6. 容易踩坑误区澄清❌误区1能不能用小根堆可以但逻辑不如大根堆直观。核心思想依然是不断压缩最大值。❌误区2为什么不尝试把最小值变大因为所有数字已经取到上限规则不允许任何数字继续变大这条路完全堵死。❌误区3会不会某个数多次除以2之后产生新的更小min_val会所以每次插入新数值时都要同步更新全局min_val。如果你需要我可以把Python / C 标准实现附带详细注释一并给出。