以下是 LeetCode 3505. 使 K 个子数组内元素相等的最少操作数的 Rust 实现---思路概述本题是 LeetCode 462最小操作次数使数组元素相等 II和 LeetCode 480滑动窗口中位数的结合题。核心思路1. 中位数贪心对于一个子数组要使其所有元素相等且操作次数最少最终值应取子数组的中位数。2. 滑动窗口中位数用对顶堆两个 BTreeMap 延迟删除维护长度为 x 的滑动窗口快速求出每个窗口变为相等的最小操作次数 cost[i]。3. 划分型 DPdp[i][j] 表示前 i 个元素中选出 j 个不重叠的长度为 x 的子数组的最小操作数。---完整 Rust 代码rustuse std::collections::BTreeMap;struct DualHeap {small: BTreeMapi32, i32, // max-heap for smaller half (largest at end)large: BTreeMapi32, i32, // min-heap for larger half (smallest at start)delayed: BTreeMapi32, i32, // lazy deletion mapsmall_size: i32,large_size: i32,small_sum: i64,large_sum: i64,small_target: i32,large_target: i32,}impl DualHeap {fn new(k: i32) - Self {DualHeap {small: BTreeMap::new(),large: BTreeMap::new(),delayed: BTreeMap::new(),small_size: 0,large_size: 0,small_sum: 0,large_sum: 0,small_target: k / 2,large_target: k - k / 2,}}fn insert(mut self, num: i32) {if self.small.is_empty() || num *self.small.iter().next_back().unwrap().0 {*self.small.entry(num).or_insert(0) 1;self.small_sum num as i64;self.small_size 1;} else {*self.large.entry(num).or_insert(0) 1;self.large_sum num as i64;self.large_size 1;}self.make_balance();}fn erase(mut self, num: i32) {*self.delayed.entry(num).or_insert(0) 1;if num *self.small.iter().next_back().unwrap().0 {self.small_size - 1;self.small_sum - num as i64;if num *self.small.iter().next_back().unwrap().0 {self.prune_small();}} else {self.large_size - 1;self.large_sum - num as i64;if *self.large.iter().next().unwrap().0 num {self.prune_large();}}self.make_balance();}fn get_median(self) - i32 {*self.large.iter().next().unwrap().0}fn get_cost(self) - i64 {let median self.get_median();let cost_small median as i64 * self.small_size as i64 - self.small_sum;let cost_large self.large_sum - median as i64 * self.large_size as i64;cost_small cost_large}fn make_balance(mut self) {if self.small_size self.small_target {let (num, cnt) self.small.iter().next_back().unwrap();if cnt 1 {self.small.remove(num);} else {self.small.insert(num, cnt - 1);}self.small_sum - num as i64;self.small_size - 1;*self.large.entry(num).or_insert(0) 1;self.large_sum num as i64;self.large_size 1;self.prune_small();} else if self.large_size self.large_target {let (num, cnt) self.large.iter().next().unwrap();if cnt 1 {self.large.remove(num);} else {self.large.insert(num, cnt - 1);}self.large_sum - num as i64;self.large_size - 1;*self.small.entry(num).or_insert(0) 1;self.small_sum num as i64;self.small_size 1;self.prune_large();}}fn prune_small(mut self) {while let Some((num, cnt)) self.small.iter().next_back() {if let Some(dc) self.delayed.get(num) {if dc 0 {if dc 1 {self.delayed.remove(num);} else {self.delayed.insert(num, dc - 1);}if cnt 1 {self.small.remove(num);} else {self.small.insert(num, cnt - 1);}} else {break;}} else {break;}}}fn prune_large(mut self) {while let Some((num, cnt)) self.large.iter().next() {if let Some(dc) self.delayed.get(num) {if dc 0 {if dc 1 {self.delayed.remove(num);} else {self.delayed.insert(num, dc - 1);}if cnt 1 {self.large.remove(num);} else {self.large.insert(num, cnt - 1);}} else {break;}} else {break;}}}}struct Solution;impl Solution {pub fn min_operations(nums: Veci32, x: i32, k: i32) - i64 {let n nums.len();let x x as usize;let k k as usize;let inf: i64 1e18 as i64;let mut cost vec![inf; n];let mut dh DualHeap::new(x as i32);for i in 0..x {dh.insert(nums[i]);}cost[x - 1] dh.get_cost();for i in x..n {dh.insert(nums[i]);dh.erase(nums[i - x]);cost[i] dh.get_cost();}let mut dp vec![vec![inf; k 1]; n 1];dp[0][0] 0;for i in 1..n {for j in 0..k {dp[i][j] dp[i - 1][j];if i x j 1 cost[i - 1] inf {dp[i][j] dp[i][j].min(dp[i - x][j - 1] cost[i - 1]);}}}dp[n][k]}}---复杂度分析项目 复杂度时间 O(n log x · k) — 滑动窗口 O(n log x)DP O(nk)空间 O(n x nk) — cost 数组 O(n)对顶堆 O(x)DP 数组 O(nk)由于 k ≤ 15nk 最大约为 1.5 × 10⁶空间可接受。---下载链接[LeetCode3505.rs](sandbox:///mnt/agents/output/LeetCode3505.rs)