LeetCode 1769 移动所有球到每个盒子所需的最少操作数：暴力、前缀和与两趟遍历全解（NeetCode 解法库）

LeetCode 1769 移动所有球到每个盒子所需的最少操作数：暴力、前缀和与两趟遍历全解（NeetCode 解法库）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以仓库 articles/minimum-number-of-operations-to-move-all-balls-to-each-box.md 为骨架，系统讲解 LeetCode 第 1769 题「移动所有球到每个盒子所需的最少操作数」的三种递进解法：朴素暴力法、前缀和法与最优的两趟遍历法。读完本文，你将掌握如何用 O(n) 时间一次性求出每个盒子作为汇聚点时所有球移动的总代价，并能将其中的「前缀和 + 左右两次扫描」技巧迁移到仓库内其他同类问题（如 Product of Array Except Self、Find Pivot Index）上。

问题概述

给定一个长度为n的二进制字符串boxes，其中boxes[i]为'0'表示第i个盒子为空，为'1'表示该盒子中有且只有一个球。一次操作可以把某个球向左或向右移动一个盒子。

对每个位置pos（0 ≤ pos < n），需要回答：把所有球都移动到第pos个盒子所需的最少操作数。最终返回一个长度为n的数组res，其中res[pos]即对应答案。

核心观察：把球从位置i移动到位置pos的代价恰好是两者下标的绝对距离|pos - i|，因此res[pos] = Σ |pos - i|（对所有满足boxes[i] == '1'的i求和）。问题本质是：对一维坐标轴上的若干"质量点"，求它们到每个整数坐标点的加权距离和。

前置知识

开始编码前，需要熟悉以下三项基础能力：

• 数组遍历（Array Traversal）：理解如何迭代数组并维护累计值，是本题所有解法的前提。
• 前缀和（Prefix Sums）：优化解法利用前缀和高效计算来自左侧与右侧的贡献，避免重复扫描。
• 两趟遍历（Two-Pass Technique）：最优方案从左到右、从右到左各扫描一次数组，在两次遍历中完成全部贡献的累加。

解法一：暴力法（Brute Force）—— O(n²)

思路

对于每个目标盒子pos，直接遍历所有盒子：凡是有球的盒子i，就把距离|pos - i|累加到res[pos]。这完全按照题面定义逐项计算，是最直观、最不容易出错的写法。

算法步骤

1. 创建长度为n的结果数组res，初始化为 0。
2. 对每个目标位置pos（外层循环）：
   • 遍历所有盒子i（内层循环）。
   • 若boxes[i] == '1'，执行res[pos] += abs(pos - i)。
3. 返回res。

多语言实现

class Solution: def minOperations(self, boxes: str) -> List[int]: n = len(boxes) res = [0] * n for pos in range(n): for i in range(n): if boxes[i] == '1': res[pos] += abs(pos - i) return res

public class Solution { public int[] minOperations(String boxes) { int n = boxes.length(); int[] res = new int[n]; for (int pos = 0; pos < n; pos++) { for (int i = 0; i < n; i++) { if (boxes.charAt(i) == '1') { res[pos] += Math.abs(pos - i); } } } return res; } }

class Solution { public: vector<int> minOperations(string boxes) { int n = boxes.size(); vector<int> res(n, 0); for (int pos = 0; pos < n; pos++) { for (int i = 0; i < n; i++) { if (boxes[i] == '1') { res[pos] += abs(pos - i); } } } return res; } };

class Solution { /** * @param {string} boxes * @return {number[]} */ minOperations(boxes) { const n = boxes.length; const res = new Array(n).fill(0); for (let pos = 0; pos < n; pos++) { for (let i = 0; i < n; i++) { if (boxes[i] === '1') { res[pos] += Math.abs(pos - i); } } } return res; } }

public class Solution { public int[] MinOperations(string boxes) { int n = boxes.Length; int[] res = new int[n]; for (int pos = 0; pos < n; pos++) { for (int i = 0; i < n; i++) { if (boxes[i] == '1') { res[pos] += Math.Abs(pos - i); } } } return res; } }

func minOperations(boxes string) []int { n := len(boxes) res := make([]int, n) for pos := 0; pos < n; pos++ { for i := 0; i < n; i++ { if boxes[i] == '1' { if pos > i { res[pos] += pos - i } else { res[pos] += i - pos } } } } return res }

class Solution { fun minOperations(boxes: String): IntArray { val n = boxes.length val res = IntArray(n) for (pos in 0 until n) { for (i in 0 until n) { if (boxes[i] == '1') { res[pos] += kotlin.math.abs(pos - i) } } } return res } }

class Solution { func minOperations(_ boxes: String) -> [Int] { let n = boxes.count var res = Int let chars = Array(boxes) for pos in 0..<n { for i in 0..<n { if chars[i] == "1" { res[pos] += abs(pos - i) } } } return res } }

impl Solution { pub fn min_operations(boxes: String) -> Vec<i32> { let n = boxes.len(); let bytes = boxes.as_bytes(); let mut res = vec![0; n]; for pos in 0..n { for i in 0..n { if bytes[i] == b'1' { res[pos] += (pos as i32 - i as i32).abs(); } } } res } }

class Solution { /** * @param {string} boxes * @return {number[]} */ minOperations(boxes: string): number[] { const n = boxes.length; const res: number[] = new Array(n).fill(0); for (let pos = 0; pos < n; pos++) { for (let i = 0; i < n; i++) { if (boxes[i] === '1') { res[pos] += Math.abs(pos - i); } } } return res; } }

复杂度分析

• 时间复杂度：O(n²)。外层 n 个位置 × 内层 n 个盒子。
• 空间复杂度：O(1) 额外空间（不含输出数组）；输出数组本身占用 O(n)。

暴力法在n较大时（本题数据范围可到 2000）仍可接受，但它重复计算了大量信息：相邻位置pos与pos + 1的结果高度相关，却被各自独立地完整扫描了一遍。

解法二：前缀和（Prefix Sum）—— O(n)

思路

把res[i]拆成左侧贡献与右侧贡献两部分：

• 对位置i左侧的球：每个球到i的距离为i - index，总和为i * count_left - sum_of_indices_left；
• 对位置i右侧的球：每个球到i的距离为index - i，总和为sum_of_indices_right - i * count_right。

因此只需要预先求出两类前缀信息——球的个数前缀和与球下标之和前缀和——就能在 O(1) 时间内算出任意位置i的左右贡献。

算法步骤

1. 构建两个前缀数组（长度为n + 1）：
   • prefix_count[i]= 盒子0到i-1中球的个数；
   • index_sum[i]= 盒子0到i-1中所有球的下标之和。
2. 对每个位置i：
   • 左侧贡献 =i * left_count - left_sum；
   • 右侧贡献 =right_sum - i * right_count；
   • 两者相加写入res[i]。
3. 返回res。

其中left_count = prefix_count[i]、left_sum = index_sum[i]直接取自前缀数组；右侧信息用总前缀减去当前位置之后的前缀得到：right_count = prefix_count[n] - prefix_count[i + 1]、right_sum = index_sum[n] - index_sum[i + 1]。

多语言实现

class Solution: def minOperations(self, boxes: str) -> List[int]: n = len(boxes) res = [0] * n prefix_count = [0] * (n + 1) index_sum = [0] * (n + 1) for i in range(n): prefix_count[i + 1] = prefix_count[i] + (boxes[i] == '1') index_sum[i + 1] = index_sum[i] + (i if boxes[i] == '1' else 0) for i in range(n): left = prefix_count[i] left_sum = index_sum[i] right = prefix_count[n] - prefix_count[i + 1] right_sum = index_sum[n] - index_sum[i + 1] res[i] = (i * left - left_sum) + (right_sum - i * right) return res

public class Solution { public int[] minOperations(String boxes) { int n = boxes.length(); int[] res = new int[n]; int[] prefixCount = new int[n + 1]; int[] indexSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixCount[i + 1] = prefixCount[i] + (boxes.charAt(i) == '1' ? 1 : 0); indexSum[i + 1] = indexSum[i] + (boxes.charAt(i) == '1' ? i : 0); } for (int i = 0; i < n; i++) { int left = prefixCount[i]; int leftSum = indexSum[i]; int right = prefixCount[n] - prefixCount[i + 1]; int rightSum = indexSum[n] - indexSum[i + 1]; res[i] = i * left - leftSum + (rightSum - i * right); } return res; } }

class Solution { public: vector<int> minOperations(string boxes) { int n = boxes.size(); vector<int> res(n), prefixCount(n + 1, 0), indexSum(n + 1, 0); for (int i = 0; i < n; i++) { prefixCount[i + 1] = prefixCount[i] + (boxes[i] == '1' ? 1 : 0); indexSum[i + 1] = indexSum[i] + (boxes[i] == '1' ? i : 0); } for (int i = 0; i < n; i++) { int left = prefixCount[i]; int leftSum = indexSum[i]; int right = prefixCount[n] - prefixCount[i + 1]; int rightSum = indexSum[n] - indexSum[i + 1]; res[i] = i * left - leftSum + (rightSum - i * right); } return res; } };

class Solution { /** * @param {string} boxes * @return {number[]} */ minOperations(boxes) { const n = boxes.length; const res = new Array(n).fill(0); const prefixCount = new Array(n + 1).fill(0); const indexSum = new Array(n + 1).fill(0); for (let i = 0; i < n; i++) { prefixCount[i + 1] = prefixCount[i] + (boxes[i] === '1' ? 1 : 0); indexSum[i + 1] = indexSum[i] + (boxes[i] === '1' ? i : 0); } for (let i = 0; i < n; i++) { const left = prefixCount[i]; const leftSum = indexSum[i]; const right = prefixCount[n] - prefixCount[i + 1]; const rightSum = indexSum[n] - indexSum[i + 1]; res[i] = i * left - leftSum + (rightSum - i * right); } return res; } }

public class Solution { public int[] MinOperations(string boxes) { int n = boxes.Length; int[] res = new int[n]; int[] prefixCount = new int[n + 1]; int[] indexSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixCount[i + 1] = prefixCount[i] + (boxes[i] == '1' ? 1 : 0); indexSum[i + 1] = indexSum[i] + (boxes[i] == '1' ? i : 0); } for (int i = 0; i < n; i++) { int left = prefixCount[i]; int leftSum = indexSum[i]; int right = prefixCount[n] - prefixCount[i + 1]; int rightSum = indexSum[n] - indexSum[i + 1]; res[i] = i * left - leftSum + (rightSum - i * right); } return res; } }

func minOperations(boxes string) []int { n := len(boxes) res := make([]int, n) prefixCount := make([]int, n+1) indexSum := make([]int, n+1) for i := 0; i < n; i++ { if boxes[i] == '1' { prefixCount[i+1] = prefixCount[i] + 1 indexSum[i+1] = indexSum[i] + i } else { prefixCount[i+1] = prefixCount[i] indexSum[i+1] = indexSum[i] } } for i := 0; i < n; i++ { left := prefixCount[i] leftSum := indexSum[i] right := prefixCount[n] - prefixCount[i+1] rightSum := indexSum[n] - indexSum[i+1] res[i] = i*left - leftSum + (rightSum - i*right) } return res }

class Solution { fun minOperations(boxes: String): IntArray { val n = boxes.length val res = IntArray(n) val prefixCount = IntArray(n + 1) val indexSum = IntArray(n + 1) for (i in 0 until n) { prefixCount[i + 1] = prefixCount[i] + if (boxes[i] == '1') 1 else 0 indexSum[i + 1] = indexSum[i] + if (boxes[i] == '1') i else 0 } for (i in 0 until n) { val left = prefixCount[i] val leftSum = indexSum[i] val right = prefixCount[n] - prefixCount[i + 1] val rightSum = indexSum[n] - indexSum[i + 1] res[i] = i * left - leftSum + (rightSum - i * right) } return res } }

class Solution { func minOperations(_ boxes: String) -> [Int] { let n = boxes.count var res = Int var prefixCount = Int var indexSum = Int let chars = Array(boxes) for i in 0..<n { prefixCount[i + 1] = prefixCount[i] + (chars[i] == "1" ? 1 : 0) indexSum[i + 1] = indexSum[i] + (chars[i] == "1" ? i : 0) } for i in 0..<n { let left = prefixCount[i] let leftSum = indexSum[i] let right = prefixCount[n] - prefixCount[i + 1] let rightSum = indexSum[n] - indexSum[i + 1] res[i] = i * left - leftSum + (rightSum - i * right) } return res } }

impl Solution { pub fn min_operations(boxes: String) -> Vec<i32> { let n = boxes.len(); let bytes = boxes.as_bytes(); let mut res = vec![0i32; n]; let mut prefix_count = vec![0i32; n + 1]; let mut index_sum = vec![0i32; n + 1]; for i in 0..n { let is_one = if bytes[i] == b'1' { 1 } else { 0 }; prefix_count[i + 1] = prefix_count[i] + is_one; index_sum[i + 1] = index_sum[i] + if bytes[i] == b'1' { i as i32 } else { 0 }; } for i in 0..n { let left = prefix_count[i]; let left_sum = index_sum[i]; let right = prefix_count[n] - prefix_count[i + 1]; let right_sum = index_sum[n] - index_sum[i + 1]; res[i] = i as i32 * left - left_sum + (right_sum - i as i32 * right); } res } }

class Solution { /** * @param {string} boxes * @return {number[]} */ minOperations(boxes: string): number[] { const n = boxes.length; const res: number[] = new Array(n).fill(0); const prefixCount: number[] = new Array(n + 1).fill(0); const indexSum: number[] = new Array(n + 1).fill(0); for (let i = 0; i < n; i++) { prefixCount[i + 1] = prefixCount[i] + (boxes[i] === '1' ? 1 : 0); indexSum[i + 1] = indexSum[i] + (boxes[i] === '1' ? i : 0); } for (let i = 0; i < n; i++) { const left = prefixCount[i]; const leftSum = indexSum[i]; const right = prefixCount[n] - prefixCount[i + 1]; const rightSum = indexSum[n] - indexSum[i + 1]; res[i] = i * left - leftSum + (rightSum - i * right); } return res; } }

复杂度分析

• 时间复杂度：O(n)。构建前缀数组 O(n)，逐位计算 O(n)。
• 空间复杂度：O(n)。两个长度n + 1的前缀数组。

这种「维护前缀个数与前缀下标和」的思想与仓库内 Find Pivot Index 一文的左右和拆分一脉相承，是前缀和思想的又一典型应用。

解法三：前缀和最优版（两趟遍历）—— O(n) 时间、O(1) 额外空间

思路

解法二用两个前缀数组换来了 O(1) 的查询，但能否把空间也压到 O(1)？关键在于观察相邻位置之间结果的增量关系：

从左向右扫描时，想象所有已扫描到的球每"向前推进一个位置"，它们到当前盒子的距离总和就会增加"球的个数"。于是可以维护两个滚动变量：

• balls：已经看到的球的总数；
• moves：把这些球全部移到当前位置所需的累计操作数。

每次到达新位置i时，moves就是左侧所有球到i的贡献，直接累加到res[i]；然后moves += balls（全体左侧球再右移一格），再把当前位置的球并入balls。从右向左做同样的扫描，把右侧贡献累加进res[i]。两次遍历之和即最终答案。

算法步骤

1. 从左到右的遍历：
   • 初始化balls = 0, moves = 0。
   • 对每个位置i：res[i] = balls + moves；随后moves += balls；最后若boxes[i] == '1'则balls += 1。
   • 注意顺序：先记录结果，再更新 moves，最后并入当前球。
2. 从右到左的遍历：
   • 重置balls = 0, moves = 0。
   • 对每个位置i（从n - 1到0）：res[i] += balls + moves；随后moves += balls；最后并入当前球。
3. 返回res。

多语言实现

class Solution: def minOperations(self, boxes: str) -> List[int]: n = len(boxes) res = [0] * n balls = moves = 0 for i in range(n): res[i] = balls + moves moves += balls balls += int(boxes[i]) balls = moves = 0 for i in range(n - 1, -1, -1): res[i] += balls + moves moves += balls balls += int(boxes[i]) return res

public class Solution { public int[] minOperations(String boxes) { int n = boxes.length(); int[] res = new int[n]; int balls = 0, moves = 0; for (int i = 0; i < n; i++) { res[i] = balls + moves; moves += balls; balls += boxes.charAt(i) - '0'; } balls = moves = 0; for (int i = n - 1; i >= 0; i--) { res[i] += balls + moves; moves += balls; balls += boxes.charAt(i) - '0'; } return res; } }

class Solution { public: vector<int> minOperations(string boxes) { int n = boxes.size(); vector<int> res(n, 0); int balls = 0, moves = 0; for (int i = 0; i < n; i++) { res[i] = balls + moves; moves += balls; balls += boxes[i] - '0'; } balls = moves = 0; for (int i = n - 1; i >= 0; i--) { res[i] += balls + moves; moves += balls; balls += boxes[i] - '0'; } return res; } };

class Solution { /** * @param {string} boxes * @return {number[]} */ minOperations(boxes) { const n = boxes.length; const res = new Array(n).fill(0); let balls = 0, moves = 0; for (let i = 0; i < n; i++) { res[i] = balls + moves; moves += balls; balls += Number(boxes[i]); } balls = moves = 0; for (let i = n - 1; i >= 0; i--) { res[i] += balls + moves; moves += balls; balls += Number(boxes[i]); } return res; } }

public class Solution { public int[] MinOperations(string boxes) { int n = boxes.Length; int[] res = new int[n]; int balls = 0, moves = 0; for (int i = 0; i < n; i++) { res[i] = balls + moves; moves += balls; balls += boxes[i] - '0'; } balls = moves = 0; for (int i = n - 1; i >= 0; i--) { res[i] += balls + moves; moves += balls; balls += boxes[i] - '0'; } return res; } }

func minOperations(boxes string) []int { n := len(boxes) res := make([]int, n) balls, moves := 0, 0 for i := 0; i < n; i++ { res[i] = balls + moves moves += balls balls += int(boxes[i] - '0') } balls, moves = 0, 0 for i := n - 1; i >= 0; i-- { res[i] += balls + moves moves += balls balls += int(boxes[i] - '0') } return res }

class Solution { fun minOperations(boxes: String): IntArray { val n = boxes.length val res = IntArray(n) var balls = 0 var moves = 0 for (i in 0 until n) { res[i] = balls + moves moves += balls balls += boxes[i] - '0' } balls = 0 moves = 0 for (i in n - 1 downTo 0) { res[i] += balls + moves moves += balls balls += boxes[i] - '0' } return res } }

class Solution { func minOperations(_ boxes: String) -> [Int] { let n = boxes.count var res = Int let chars = Array(boxes) var balls = 0 var moves = 0 for i in 0..<n { res[i] = balls + moves moves += balls balls += chars[i] == "1" ? 1 : 0 } balls = 0 moves = 0 for i in stride(from: n - 1, through: 0, by: -1) { res[i] += balls + moves moves += balls balls += chars[i] == "1" ? 1 : 0 } return res } }

impl Solution { pub fn min_operations(boxes: String) -> Vec<i32> { let n = boxes.len(); let bytes = boxes.as_bytes(); let mut res = vec![0i32; n]; let mut balls = 0i32; let mut moves = 0i32; for i in 0..n { res[i] = balls + moves; moves += balls; balls += (bytes[i] - b'0') as i32; } balls = 0; moves = 0; for i in (0..n).rev() { res[i] += balls + moves; moves += balls; balls += (bytes[i] - b'0') as i32; } res } }

class Solution { /** * @param {string} boxes * @return {number[]} */ minOperations(boxes: string): number[] { const n = boxes.length; const res: number[] = new Array(n).fill(0); let balls = 0, moves = 0; for (let i = 0; i < n; i++) { res[i] = balls + moves; moves += balls; balls += Number(boxes[i]); } balls = moves = 0; for (let i = n - 1; i >= 0; i--) { res[i] += balls + moves; moves += balls; balls += Number(boxes[i]); } return res; } }

复杂度分析

• 时间复杂度：O(n)。两趟线性扫描。
• 空间复杂度：O(1) 额外空间（不含输出数组）；输出数组本身占用 O(n)。

增量计算的具体推演

以boxes = "110"为例，逐步推演第一趟（从左到右）过程：

此时res = [0, 1, 3]分别表示左侧球（下标 0、1）对位置 0、1、2 的贡献。第二趟从右到左同理累加右侧球（本题中仅位置 2 右侧无球），最终得到res = [1, 1, 3]：把两个球都移到盒子 0 需要 1 步（下标 1 的球左移 1 格），移到盒子 1 需要 1 步（下标 0 的球右移 1 格），移到盒子 2 需要 3 步。

这个「先记录、再平移、后并入」的滚动更新手法，与仓库内 Product of Array Except Self 一文中左右两次累乘得到"除自身外乘积"的思路完全同构：本质上都是把全局信息（所有球/所有元素）拆成左侧信息 + 右侧信息，用两趟遍历分别累积，最终合成完整答案。

三种解法对比

常见陷阱（Common Pitfalls）

1. 字符与整数的比较错误

输入boxes是字符串，其中每个元素是字符'0'或'1'，而不是整数。在大多数语言中，写成boxes[i] == 1而非boxes[i] == '1'会永远为false（如 Java 中 char 与 int 比较虽然合法，但字符'1'的码值是 49，不等于 1），导致算法"看不见"任何球，结果全为 0。Python、JavaScript 等语言同样需要显式区分字符与数值，可用int(boxes[i])、Number(boxes[i])或boxes[i] - '0'完成转换。

2. 两趟遍历中更新顺序错误

在最优解法中，res[i]、moves、balls三条语句的先后顺序至关重要。若在计算res[i]之前就执行balls += ...把当前位置的球并入，则当前位置自己的球会被错误地计入它到自身的移动代价（本应为 0），造成 off-by-one 误差。正确顺序永远是：先用旧状态记录结果 → 再平移 moves → 最后并入新球。

3. 左右贡献公式的越界（off-by-one）错误

使用公式i * leftCount - leftSum计算左侧贡献时，前缀数组是 0 基还是 1 基、用i还是i + 1取前缀值，会整体平移所有计算。务必先明确prefix[k]的语义（本解法约定为"前 k 个盒子"的信息），再核对左边界prefix[i]与右边界prefix[n] - prefix[i + 1]是否分别对应[0, i)与(i, n)两个开区间，确保当前盒子i既不重复计、也不被遗漏。

总结

「Minimum Number of Operations to Move All Balls to Each Box」是练习前缀和与两趟遍历的经典题目：暴力法帮助建立直觉，前缀和法展示信息复用，两趟遍历法则把空间压到 O(1)。掌握这一"左右拆解 + 增量更新"的思维模式后，可以顺藤摸瓜继续阅读仓库中的 Find Pivot Index（前缀和的左右和比较）与 Product of Array Except Self（两趟累乘）等文章，它们共享同一套方法论，一通百通。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode