这道题的核心在于数学转化 动态维护中位数。下面是解题思路与完整的 Rust 实现。核心解题思路1. 问题转化最终需要满足 nums[a1] nums[a] 1。对于前 i 个元素等价于将 nums[t] - t 变为同一个数 x。例如 nums[1] 要变成 x1等价于把 nums[1]-1 变成 x。2. 最小代价将一串数变成同一个数 x 的最小总操作数是当 x 取这串数的中位数时取得的。因此问题转化为对每个前缀 [0..i]求数组 b[t] nums[t] - t 的中位数并计算所有 b[t] 到中位数的距离之和。3. 动态维护中位数对顶堆使用两个堆来动态维护中位数· 大根堆 (lower)保存较小的一半元素堆顶是这部分的最大值。· 小根堆 (upper)保存较大的一半元素堆顶是这部分的最小值。· 维护 lower 的大小等于 upper 的大小或比它多 1。这样 lower 的堆顶就是当前数据流的中位数。· 同时维护 lower_sum 和 upper_sum 来快速计算距离和。Rust 实现rustuse std::collections::BinaryHeap;use std::cmp::Reverse;impl Solution {pub fn nums_game(nums: Veci32) - Veci32 {const MOD: i64 1_000_000_007;let n nums.len();let mut ans Vec::with_capacity(n);// 大根堆存较小的一半使用 Reverse 实现最大堆let mut lower BinaryHeap::new();// 小根堆存较大的一半let mut upper BinaryHeap::new();let mut lower_sum: i64 0;let mut upper_sum: i64 0;for (i, num) in nums.iter().enumerate() {// 关键转化nums[i] - ilet x (num - i as i32) as i64;// 1. 将新元素 x 插入到合适的堆中if lower.is_empty() || lower.peek().unwrap() x {lower.push(x);lower_sum x;} else {upper.push(Reverse(x));upper_sum x;}// 2. 平衡两个堆的大小保证 lower 的大小 upper 的大小// 且 lower 的大小最多比 upper 大 1if lower.len() upper.len() 1 {// lower 太大了把堆顶最大值移到 upperif let Some(top) lower.pop() {lower_sum - top;upper.push(Reverse(top));upper_sum top;}} else if upper.len() lower.len() {// upper 太大了把堆顶最小值移到 lowerif let Some(Reverse(top)) upper.pop() {upper_sum - top;lower.push(top);lower_sum top;}}// 3. 计算当前前缀的最小操作数let res if (i 1) % 2 0 {// 偶数个元素中位数可以是中间两个数的任意值这里用 upper 的最小值// 代价 upper_sum - lower_sum(upper_sum - lower_sum) % MOD} else {// 奇数个元素中位数是 lower 的最大值// 代价 (upper_sum - lower_sum) lower.peek().unwrap()let median *lower.peek().unwrap();(upper_sum - lower_sum median) % MOD};// 确保结果非负ans.push(((res % MOD MOD) % MOD) as i32);}ans}}复杂度分析· 时间复杂度: O(n log n)其中 n 是数组长度。每个元素执行常数次堆的插入和删除操作。· 空间复杂度: O(n)用于存储两个堆。总结这个实现将复杂的数列操作问题通过 nums[i] - i 的转化变成了经典的中位数问题并利用两个堆对顶堆在遍历过程中动态维护中位数从而高效地计算出每个前缀的最小操作数。
这道题的核心在于数学转化 动态维护中位数。下面是解题思路与完整的 Rust 实现。核心解题思路1. 问题转化最终需要满足 nums[a1] nums[a] 1。对于前 i 个元素等价于将 nums[t] - t 变为同一个数 x。例如 nums[1] 要变成 x1等价于把 nums[1]-1 变成 x。2. 最小代价将一串数变成同一个数 x 的最小总操作数是当 x 取这串数的中位数时取得的。因此问题转化为对每个前缀 [0..i]求数组 b[t] nums[t] - t 的中位数并计算所有 b[t] 到中位数的距离之和。3. 动态维护中位数对顶堆使用两个堆来动态维护中位数· 大根堆 (lower)保存较小的一半元素堆顶是这部分的最大值。· 小根堆 (upper)保存较大的一半元素堆顶是这部分的最小值。· 维护 lower 的大小等于 upper 的大小或比它多 1。这样 lower 的堆顶就是当前数据流的中位数。· 同时维护 lower_sum 和 upper_sum 来快速计算距离和。Rust 实现rustuse std::collections::BinaryHeap;use std::cmp::Reverse;impl Solution {pub fn nums_game(nums: Veci32) - Veci32 {const MOD: i64 1_000_000_007;let n nums.len();let mut ans Vec::with_capacity(n);// 大根堆存较小的一半使用 Reverse 实现最大堆let mut lower BinaryHeap::new();// 小根堆存较大的一半let mut upper BinaryHeap::new();let mut lower_sum: i64 0;let mut upper_sum: i64 0;for (i, num) in nums.iter().enumerate() {// 关键转化nums[i] - ilet x (num - i as i32) as i64;// 1. 将新元素 x 插入到合适的堆中if lower.is_empty() || lower.peek().unwrap() x {lower.push(x);lower_sum x;} else {upper.push(Reverse(x));upper_sum x;}// 2. 平衡两个堆的大小保证 lower 的大小 upper 的大小// 且 lower 的大小最多比 upper 大 1if lower.len() upper.len() 1 {// lower 太大了把堆顶最大值移到 upperif let Some(top) lower.pop() {lower_sum - top;upper.push(Reverse(top));upper_sum top;}} else if upper.len() lower.len() {// upper 太大了把堆顶最小值移到 lowerif let Some(Reverse(top)) upper.pop() {upper_sum - top;lower.push(top);lower_sum top;}}// 3. 计算当前前缀的最小操作数let res if (i 1) % 2 0 {// 偶数个元素中位数可以是中间两个数的任意值这里用 upper 的最小值// 代价 upper_sum - lower_sum(upper_sum - lower_sum) % MOD} else {// 奇数个元素中位数是 lower 的最大值// 代价 (upper_sum - lower_sum) lower.peek().unwrap()let median *lower.peek().unwrap();(upper_sum - lower_sum median) % MOD};// 确保结果非负ans.push(((res % MOD MOD) % MOD) as i32);}ans}}复杂度分析· 时间复杂度: O(n log n)其中 n 是数组长度。每个元素执行常数次堆的插入和删除操作。· 空间复杂度: O(n)用于存储两个堆。总结这个实现将复杂的数列操作问题通过 nums[i] - i 的转化变成了经典的中位数问题并利用两个堆对顶堆在遍历过程中动态维护中位数从而高效地计算出每个前缀的最小操作数。
-model_runner)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
