LeetCode-Go 题解1675. Minimize Deviation in Array 最小化数组偏移量的双阶段贪心实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 开源仓库中 leetcode/1675.Minimize-Deviation-in-Array/README.md 的官方题解深入拆解 LeetCode 第 1675 题「Minimize Deviation in Array」的数学本质与 Go 实现。文章结合 实现源码 与 单元测试讲解奇偶归一 贪心收缩最大值的两阶段算法帮助读者掌握处理乘 2 / 除 2 变换 极差最小化类题目的通用套路。题目回顾给定一个由n个正整数组成的数组nums你可以对任意元素执行任意次数的两类操作如果元素是偶数将其除以 2。例如[1,2,3,4]对最后一个元素操作后变为[1,2,3,2]如果元素是奇数将其乘以 2。例如[1,2,3,4]对第一个元素操作后变为[2,2,3,4]。数组的偏移量Deviation定义为数组中任意两个元素之间的最大差值即max(nums) - min(nums)。要求返回数组在执行若干次操作之后能够达到的最小偏移量。输入输出示例示例 1Input: nums [1,2,3,4] Output: 1 Explanation: 可先将数组变为 [1,2,3,2]再变为 [2,2,3,2]此时偏移量为 3 - 2 1。示例 2Input: nums [4,1,5,20,3] Output: 3 Explanation: 经过两次操作可将数组变为 [4,2,5,5,3]此时偏移量为 5 - 2 3。示例 3Input: nums [2,10,8] Output: 3数据约束n nums.length2 n 10^51 nums[i] 10^9nums[i]最大可达10^9且n可达10^5意味着算法必须在线性到O(n log U)U为元素值规模级别内完成任何指数级枚举都是不可接受的。解题思路奇偶归一 贪心收缩核心观察两种操作的本质是乘 2 / 除 2的往返要找到最小偏移量本质上是想让最大值变小、最小值变大。题目给的两种操作恰好对应两个方向奇数乘 2 —— 可以让最小值变大偶数除 2 —— 可以让最大值变小。这里有一个关键的数学特性奇数一旦乘以 2 就变成了偶数而偶数除以 2 之后可能是奇数也可能是偶数。也就是说对于一个奇数x它能取到的值只有x和2x两种而它的倍数形态2x仍然可能通过不断除 2 回到x。利用这一特性可以设计出两阶段算法第一阶段奇偶归一All-Odd to Even先把数组中所有奇数都乘以 2 统一变成偶数。为什么这一步是安全的因为奇数x能到达的状态集合是{x, 2x}而乘以 2 后的2x是一个偶数后续可以通过除 2 再变回x。也就是说把奇数先变成偶数不会丢失任何可达状态却把整个数组统一到了一个全是偶数的闭区间里让后续的所有操作退化为只有除 2 一种操作问题被大幅简化。这一步同样完成对当前数组min与max的初始化扫描并计算出初始偏移量res max - min作为答案的候选上界。第二阶段贪心收缩最大值Shrink the Maximum进入循环只要当前最大值max还是偶数即还能继续除 2就做一轮收缩找出本轮中可以除以 2 的元素并执行除法判定条件为该元素等于当前最大值max把最大的偶数除下去直接压低上界或该元素是偶数且除以 2 后不小于当前最小值min即min nums[i]/2说明除下去不会跌破最小值、不会扩大偏移量。重新扫描计算本轮新的tmin与tmax更新偏移量候选res。更新min、max进入下一轮。循环终止条件是最大值为奇数——此时它无法再除 2整个收缩过程结束。最终返回过程中记录到的最小偏移量res。一个常见疑问为什么只缩小最大值而不主动放大最小值这是本题最容易困惑的地方原题解给出了非常严谨的回答如果当前最小值是奇数它一定是由某个偶数除以 2变过来的因为在第一阶段所有奇数都已被乘成偶数。也就是说这个奇数的最小值状态在上一轮循环中已经被计算过了上一轮它还是更大的偶数因此在当前轮完全没有必要再把它乘回去放大——那只会把已经枚举过的状态重复计算一遍。如果当前最小值是偶数它不会满足min nums[i]/2这个条件即它永远不会在除 2 的操作中被继续除下去。因为一旦把它除以 2数组最小值就会被进一步拉低反而扩大偏移量这与我们的目标相悖。所以贪心策略下它天然会被跳过。综合来看最小值永远不会被错误地缩小也不需要被主动放大每一步收缩最大值的决策都是安全的这就是该算法正确性的关键所在。代码实现与源码级解读仓库中的核心实现位于 1675. Minimize Deviation in Array.go完整代码如下package leetcode func minimumDeviation(nums []int) int { min, max : 0, 0 for i : range nums { if nums[i]%2 1 { nums[i] * 2 } if i 0 { min nums[i] max nums[i] } else if nums[i] min { min nums[i] } else if max nums[i] { max nums[i] } } res : max - min for max%2 0 { tmax, tmin : 0, 0 for i : range nums { if nums[i] max || (nums[i]%2 0 min nums[i]/2) { nums[i] / 2 } if i 0 { tmin nums[i] tmax nums[i] } else if nums[i] tmin { tmin nums[i] } else if tmax nums[i] { tmax nums[i] } } if tmax-tmin res { res tmax - tmin } min, max tmin, tmax } return res }代码要点逐行拆解第一阶段第 417 行遍历nums遇到奇数nums[i]%2 1立即乘 2同时借助i 0初始化min、max之后用两次比较完成单遍扫描求出全偶数组的极值并记录初始偏移量res。第二阶段第 1938 行外层for max%2 0保证只要最大值还能除就继续内层循环中nums[i] max命中当前上界无条件除 2压低最大值nums[i]%2 0 min nums[i]/2命中偶数且除后不跌破当前最小值的元素一并除 2——这正是原题解中提到的把第一步奇数乘 2 还原回去和把本来的偶数继续除下去这两个目的的统一实现内层循环同样在单遍扫描中完成新极值tmin、tmax的统计随后用tmax-tmin res贪心式地更新最优答案并把极值滚动给下一轮。复杂度分析每个元素从奇数×2 后的最大值开始只会被不断除 2 直到变成奇数元素x最多被除O(log x)次总轮数受最大值的二进制位数限制整体时间复杂度约为O(n log max(nums))空间复杂度为O(1)原地修改输入数组。在n 10^5、nums[i] 10^9的约束下可以轻松通过。单元测试验证仓库为本题配套了标准测试用例见 1675. Minimize Deviation in Array_test.goqs : []question1675{ { para1675{[]int{1, 2, 4, 3}}, ans1675{1}, }, { para1675{[]int{4, 1, 5, 20, 3}}, ans1675{3}, }, { para1675{[]int{2, 10, 8}}, ans1675{3}, }, { para1675{[]int{8, 2, 10}}, ans1675{3}, }, }除题目给出的三个官方示例外测试还额外覆盖了[8, 2, 10]这一乱序变体用于验证算法对数组原始顺序不敏感结果仍为 3增强了用例的健壮性。测试遵循仓库统一的question para ans表驱动风格与仓库其他题目如 0001.Two-Sum 等目录的测试组织方式一致。可以通过仓库根目录的 gotest.sh 脚本对全部 leetcode 包执行测试与覆盖率收集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可单独运行本题测试go test -v -run Test_Problem1675 ./leetcode/1675.Minimize-Deviation-in-Array/运行后可看到类似【input】:[1 2 4 3] 【output】:1的输出日志与预期答案逐一对应。进阶思考另一种常见解法最大堆从两阶段算法的思想出发还可以推导出业界更主流的解法同样先奇偶归一然后把所有偶数放入最大堆循环执行弹出最大值 → 若为偶数则除以 2 再压回堆 → 更新答案直到堆顶变为奇数。该写法利用堆自动维护当前最大值省去了每次全数组扫描思路与本文的贪心收缩完全等价只是用数据结构换掉了线性扫描——从源码结构看本文采用的双极值扫描实现以O(1)空间换取更直白的可读性适合面试中先讲清楚贪心本质再进阶到堆优化。总结1675 题的核心价值在于两处状态空间压缩认识到奇数×2 后仍可除 2 还原从而把所有数统一到偶数域将两种操作化简为一种贪心正确性论证证明最小值无需主动放大——奇数最小值是已被枚举过的历史状态偶数最小值不会被错误地继续除小。掌握了这两点就能以O(n log max)的代价解决该题。本仓库的 README.md 还按数据结构与算法对全部题解进行了分类编排读者可以沿着数组、贪心等主题继续深入练习同类问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：1675. Minimize Deviation in Array 最小化数组偏移量的双阶段贪心实现
LeetCode-Go 题解1675. Minimize Deviation in Array 最小化数组偏移量的双阶段贪心实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 开源仓库中 leetcode/1675.Minimize-Deviation-in-Array/README.md 的官方题解深入拆解 LeetCode 第 1675 题「Minimize Deviation in Array」的数学本质与 Go 实现。文章结合 实现源码 与 单元测试讲解奇偶归一 贪心收缩最大值的两阶段算法帮助读者掌握处理乘 2 / 除 2 变换 极差最小化类题目的通用套路。题目回顾给定一个由n个正整数组成的数组nums你可以对任意元素执行任意次数的两类操作如果元素是偶数将其除以 2。例如[1,2,3,4]对最后一个元素操作后变为[1,2,3,2]如果元素是奇数将其乘以 2。例如[1,2,3,4]对第一个元素操作后变为[2,2,3,4]。数组的偏移量Deviation定义为数组中任意两个元素之间的最大差值即max(nums) - min(nums)。要求返回数组在执行若干次操作之后能够达到的最小偏移量。输入输出示例示例 1Input: nums [1,2,3,4] Output: 1 Explanation: 可先将数组变为 [1,2,3,2]再变为 [2,2,3,2]此时偏移量为 3 - 2 1。示例 2Input: nums [4,1,5,20,3] Output: 3 Explanation: 经过两次操作可将数组变为 [4,2,5,5,3]此时偏移量为 5 - 2 3。示例 3Input: nums [2,10,8] Output: 3数据约束n nums.length2 n 10^51 nums[i] 10^9nums[i]最大可达10^9且n可达10^5意味着算法必须在线性到O(n log U)U为元素值规模级别内完成任何指数级枚举都是不可接受的。解题思路奇偶归一 贪心收缩核心观察两种操作的本质是乘 2 / 除 2的往返要找到最小偏移量本质上是想让最大值变小、最小值变大。题目给的两种操作恰好对应两个方向奇数乘 2 —— 可以让最小值变大偶数除 2 —— 可以让最大值变小。这里有一个关键的数学特性奇数一旦乘以 2 就变成了偶数而偶数除以 2 之后可能是奇数也可能是偶数。也就是说对于一个奇数x它能取到的值只有x和2x两种而它的倍数形态2x仍然可能通过不断除 2 回到x。利用这一特性可以设计出两阶段算法第一阶段奇偶归一All-Odd to Even先把数组中所有奇数都乘以 2 统一变成偶数。为什么这一步是安全的因为奇数x能到达的状态集合是{x, 2x}而乘以 2 后的2x是一个偶数后续可以通过除 2 再变回x。也就是说把奇数先变成偶数不会丢失任何可达状态却把整个数组统一到了一个全是偶数的闭区间里让后续的所有操作退化为只有除 2 一种操作问题被大幅简化。这一步同样完成对当前数组min与max的初始化扫描并计算出初始偏移量res max - min作为答案的候选上界。第二阶段贪心收缩最大值Shrink the Maximum进入循环只要当前最大值max还是偶数即还能继续除 2就做一轮收缩找出本轮中可以除以 2 的元素并执行除法判定条件为该元素等于当前最大值max把最大的偶数除下去直接压低上界或该元素是偶数且除以 2 后不小于当前最小值min即min nums[i]/2说明除下去不会跌破最小值、不会扩大偏移量。重新扫描计算本轮新的tmin与tmax更新偏移量候选res。更新min、max进入下一轮。循环终止条件是最大值为奇数——此时它无法再除 2整个收缩过程结束。最终返回过程中记录到的最小偏移量res。一个常见疑问为什么只缩小最大值而不主动放大最小值这是本题最容易困惑的地方原题解给出了非常严谨的回答如果当前最小值是奇数它一定是由某个偶数除以 2变过来的因为在第一阶段所有奇数都已被乘成偶数。也就是说这个奇数的最小值状态在上一轮循环中已经被计算过了上一轮它还是更大的偶数因此在当前轮完全没有必要再把它乘回去放大——那只会把已经枚举过的状态重复计算一遍。如果当前最小值是偶数它不会满足min nums[i]/2这个条件即它永远不会在除 2 的操作中被继续除下去。因为一旦把它除以 2数组最小值就会被进一步拉低反而扩大偏移量这与我们的目标相悖。所以贪心策略下它天然会被跳过。综合来看最小值永远不会被错误地缩小也不需要被主动放大每一步收缩最大值的决策都是安全的这就是该算法正确性的关键所在。代码实现与源码级解读仓库中的核心实现位于 1675. Minimize Deviation in Array.go完整代码如下package leetcode func minimumDeviation(nums []int) int { min, max : 0, 0 for i : range nums { if nums[i]%2 1 { nums[i] * 2 } if i 0 { min nums[i] max nums[i] } else if nums[i] min { min nums[i] } else if max nums[i] { max nums[i] } } res : max - min for max%2 0 { tmax, tmin : 0, 0 for i : range nums { if nums[i] max || (nums[i]%2 0 min nums[i]/2) { nums[i] / 2 } if i 0 { tmin nums[i] tmax nums[i] } else if nums[i] tmin { tmin nums[i] } else if tmax nums[i] { tmax nums[i] } } if tmax-tmin res { res tmax - tmin } min, max tmin, tmax } return res }代码要点逐行拆解第一阶段第 417 行遍历nums遇到奇数nums[i]%2 1立即乘 2同时借助i 0初始化min、max之后用两次比较完成单遍扫描求出全偶数组的极值并记录初始偏移量res。第二阶段第 1938 行外层for max%2 0保证只要最大值还能除就继续内层循环中nums[i] max命中当前上界无条件除 2压低最大值nums[i]%2 0 min nums[i]/2命中偶数且除后不跌破当前最小值的元素一并除 2——这正是原题解中提到的把第一步奇数乘 2 还原回去和把本来的偶数继续除下去这两个目的的统一实现内层循环同样在单遍扫描中完成新极值tmin、tmax的统计随后用tmax-tmin res贪心式地更新最优答案并把极值滚动给下一轮。复杂度分析每个元素从奇数×2 后的最大值开始只会被不断除 2 直到变成奇数元素x最多被除O(log x)次总轮数受最大值的二进制位数限制整体时间复杂度约为O(n log max(nums))空间复杂度为O(1)原地修改输入数组。在n 10^5、nums[i] 10^9的约束下可以轻松通过。单元测试验证仓库为本题配套了标准测试用例见 1675. Minimize Deviation in Array_test.goqs : []question1675{ { para1675{[]int{1, 2, 4, 3}}, ans1675{1}, }, { para1675{[]int{4, 1, 5, 20, 3}}, ans1675{3}, }, { para1675{[]int{2, 10, 8}}, ans1675{3}, }, { para1675{[]int{8, 2, 10}}, ans1675{3}, }, }除题目给出的三个官方示例外测试还额外覆盖了[8, 2, 10]这一乱序变体用于验证算法对数组原始顺序不敏感结果仍为 3增强了用例的健壮性。测试遵循仓库统一的question para ans表驱动风格与仓库其他题目如 0001.Two-Sum 等目录的测试组织方式一致。可以通过仓库根目录的 gotest.sh 脚本对全部 leetcode 包执行测试与覆盖率收集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可单独运行本题测试go test -v -run Test_Problem1675 ./leetcode/1675.Minimize-Deviation-in-Array/运行后可看到类似【input】:[1 2 4 3] 【output】:1的输出日志与预期答案逐一对应。进阶思考另一种常见解法最大堆从两阶段算法的思想出发还可以推导出业界更主流的解法同样先奇偶归一然后把所有偶数放入最大堆循环执行弹出最大值 → 若为偶数则除以 2 再压回堆 → 更新答案直到堆顶变为奇数。该写法利用堆自动维护当前最大值省去了每次全数组扫描思路与本文的贪心收缩完全等价只是用数据结构换掉了线性扫描——从源码结构看本文采用的双极值扫描实现以O(1)空间换取更直白的可读性适合面试中先讲清楚贪心本质再进阶到堆优化。总结1675 题的核心价值在于两处状态空间压缩认识到奇数×2 后仍可除 2 还原从而把所有数统一到偶数域将两种操作化简为一种贪心正确性论证证明最小值无需主动放大——奇数最小值是已被枚举过的历史状态偶数最小值不会被错误地继续除小。掌握了这两点就能以O(n log max)的代价解决该题。本仓库的 README.md 还按数据结构与算法对全部题解进行了分类编排读者可以沿着数组、贪心等主题继续深入练习同类问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考