题目描述
思路解析
一句话答案：LeetCode 1769 移动所有球到每个盒子的最小操作数用两遍前缀扫描：相邻盒子的答案只差左右两侧的球数，左往右滚出左半代价、右往左滚出右半代价再逐位相加，把逐个盒子从头重算的 O(n²) 压到 O(n)。
每个盒子的 answer，究竟在数什么
给你一个长度 n 的二进制字符串 boxes，第 i 位是 1 表示这盒子有球、0 表示空。一步能把一个球挪到相邻盒子。answer[i] 是把所有球集中到第 i 个盒子最少走的步数，也就是所有球到 i 的距离之和；一个球从下标 j 到 i 走 abs(i 减 j) 步。题面 boxes="001011"，三个球分别在下标 2、4、5。
对每个盒子从头加一遍，账算得起吗
最直接的做法是对每个盒子单独算：遍历整串，遇球就把它到当前盒子的距离加起来。可每个盒子都要重扫全部 n 位，n 个盒子叠成两层循环，时间 O(n²)。相邻盒子间那一大堆重复加法其实是白做的——下一个盒子的答案跟这一个只差一点点。
相邻两个盒子的答案，差在哪里
把视线从单个盒子挪到相邻两个。设第 i 个盒子的步数已知，目标右移一格到第 i+1 个盒子：左边每个球离目标远一格、多走一步，右边每个球近一格、少走一步。新答案比旧答案多出「左侧球数减右侧球数」——增量不是固定加一，而是一整批球数。
左加右减方向相反，正好拆两遍分开滚：左半代价从左往右累，计数器 cnt 记目标左边有几个球，每挪一格就在上一格左半代价上再加 cnt；右半代价对称地从右往左累。两遍各扫一次，同一盒子左右两半相加就是答案。
两遍扫描里，cnt 该在哪一步更新
左遍从下标 0 起，最左没有左邻，左半代价和 cnt 都是 0。往右每到一格，先看刚跨过的前一格 boxes[i-1]：若是球，它已落到目标左边，cnt 先加一；再用更新后的 cnt 把上一格左半代价累上来。右遍对称，从下标 n-1 起往左，先看后一格 boxes[i+1] 更新 cnt 再累。
这里唯一会做反：新跨过那格的球必须先计进 cnt 再累加，因为目标挪到这格时它已站到对应一侧；先累加再更新，这格就少算一个球，整张表跟着错位。
left 和 right 两张表各长什么样
左遍从左往右，cnt 记左边球数：首格 0；下标 0、1 空着，第 1、2 格仍 0；跨过下标 2 的球后 cnt 变 1，第 3 格 = 0+1 = 1；下标 3 空，第 4 格 = 1+1 = 2；跨过下标 4 的球后 cnt 变 2，第 5 格 = 2+2 = 4。得 left = [0,0,0,1,2,4]。
右遍对称地从右往左滚一遍，得 right = [11,8,5,3,1,0]——它正是左表的镜像，可自验。两张表逐位相加：0+11、0+8、0+5、1+3、2+1、4+0 = [11,8,5,4,3,4]，与题面一致。
cnt 记的是某侧当前球数，累起来才是代价
两遍扫描各走 n 格、逐位相加又 n 次，三趟线性，时间 O(n)；left、right 加输出数组，空间 O(n)——比逐个盒子从头累加的 O(n²) 快得多。最想不清的是 cnt 的身份：它只是某一侧当前有几个球、是每挪一格答案要涨的增量，不是答案本身，真正代价是把这些 cnt 累起来的 left 或 right。边界也无需特判：单盒时没有任何一侧、两遍停在 0；全空盒的串 cnt 始终为 0、结果全 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:目标右移一格,左边每个球多走一步、右边每个球少走一步。左遍 left[i]=left[i-1]+左边球数,右遍 right[i]=right[i+1]+右边球数,合起来 answer[i]=left[i]+right[i]。
总览 · boxes = "001011"：先看清画面。上面这排是盒子 boxes,值是 0 或 1,绿色的三格下标 2、4、5 里各有一个小球,其余是空盒。右边这张表要填的是 left,表示每个盒子左半边球搬过来的代价,现在还空着。我们先从左往右扫一遍把 left 填满,再从右往左扫一遍算 right,最后两个相加就是答案。先看第 0 个盒子。
左遍 · 第 0 位起点：左遍从第 0 个盒子开始。它是最左边,左边一个盒子都没有,自然没有球需要从左边搬过来,所以 left[0] 就是 0。计数器 cnt 记的是当前盒子左边有几个球,现在也是 0。把 0 记进 left 表的第 0 格。
左遍 · 第 1 位：目标挪到第 1 个盒子。先看刚跨过的下标 0 这一格,它是空盒,没有新球加入,cnt 还是 0。目标从 0 右移到 1,左边这 0 个球每个都要多走一步,所以在上一格 left[0] = 0 的基础上再加 cnt = 0,得到 left[1] = 0。
左遍 · 第 2 位：目标挪到第 2 个盒子。先看刚跨过的下标 1 这一格,它是空盒,没有新球加入,cnt 还是 0。目标从 1 右移到 2,左边这 0 个球每个都要多走一步,所以在上一格 left[1] = 0 的基础上再加 cnt = 0,得到 left[2] = 0。
左遍 · 第 3 位：目标挪到第 3 个盒子。先看刚跨过的下标 2 这一格,它是个球,现在它落到了目标的左边,cnt 加一变成 1。目标从 2 右移到 3,左边这 1 个球每个都要多走一步,所以在上一格 left[2] = 0 的基础上再加 cnt = 1,得到 left[3] = 1。
左遍 · 第 4 位：目标挪到第 4 个盒子。先看刚跨过的下标 3 这一格,它是空盒,没有新球加入,cnt 还是 1。目标从 3 右移到 4,左边这 1 个球每个都要多走一步,所以在上一格 left[3] = 1 的基础上再加 cnt = 1,得到 left[4] = 2。
左遍 · 第 5 位：目标挪到第 5 个盒子。先看刚跨过的下标 4 这一格,它是个球,现在它落到了目标的左边,cnt 加一变成 2。目标从 4 右移到 5,左边这 2 个球每个都要多走一步,所以在上一格 left[4] = 2 的基础上再加 cnt = 2,得到 left[5] = 4。
右遍 · 第 5 位起点：左表填满后,换个方向。右遍从最右的第 5 个盒子开始,它右边没有盒子了,没有球要从右边搬过来,所以 right[5] 是 0,记右边球数的 cnt 也从 0 起。这回我们从右往左走。
右遍 · 第 4 位：目标挪到第 4 个盒子。看刚跨过的右邻居下标 5,它是个球,现在落到目标右边,cnt 加一变成 1。目标从 5 左移到 4,右边这 1 个球每个都要多走一步,所以在 right[5] = 0 上加 cnt = 1,得到 right[4] = 1。
右遍 · 第 3 位：目标挪到第 3 个盒子。看刚跨过的右邻居下标 4,它是个球,现在落到目标右边,cnt 加一变成 2。目标从 4 左移到 3,右边这 2 个球每个都要多走一步,所以在 right[4] = 1 上加 cnt = 2,得到 right[3] = 3。
右遍 · 第 2 位：目标挪到第 2 个盒子。看刚跨过的右邻居下标 3,它是空盒,cnt 保持 2。目标从 3 左移到 2,右边这 2 个球每个都要多走一步,所以在 right[3] = 3 上加 cnt = 2,得到 right[2] = 5。
右遍 · 第 1 位：目标挪到第 1 个盒子。看刚跨过的右邻居下标 2,它是个球,现在落到目标右边,cnt 加一变成 3。目标从 2 左移到 1,右边这 3 个球每个都要多走一步,所以在 right[2] = 5 上加 cnt = 3,得到 right[1] = 8。
右遍 · 第 0 位：目标挪到第 0 个盒子。看刚跨过的右邻居下标 1,它是空盒,cnt 保持 3。目标从 1 左移到 0,右边这 3 个球每个都要多走一步,所以在 right[1] = 8 上加 cnt = 3,得到 right[0] = 11。
合并 · 左右两半相加：两遍都扫完了。left = [0,0,0,1,2,4] 是每个盒子左半边的代价,right = [11,8,5,3,1,0] 是右半边的代价。现在只要把两张表对应位置相加,每个盒子的最终答案就出来了。一个一个来。
合并 · 第 0 位 answer = 11：第 0 个盒子:左半边代价 left[0] = 0,右半边代价 right[0] = 11,相加得 11。意思是把三个球全搬到最左边的 0 号盒子,一共要走 11 步。
合并 · 第 1 位 answer = 8：第 1 个盒子:左半边代价 left[1] = 0,右半边代价 right[1] = 8,相加得 8。记进 answer 的第 1 位。
合并 · 第 2 位 answer = 5：第 2 个盒子:左半边代价 left[2] = 0,右半边代价 right[2] = 5,相加得 5。记进 answer 的第 2 位。
合并 · 第 3 位 answer = 4：第 3 个盒子:左半边代价 left[3] = 1,右半边代价 right[3] = 3,相加得 4。记进 answer 的第 3 位。
合并 · 第 4 位 answer = 3：第 4 个盒子:左半边代价 left[4] = 2,右半边代价 right[4] = 1,相加得 3。记进 answer 的第 4 位。
合并 · 第 5 位 answer = 4：第 5 个盒子:左半边代价 left[5] = 4,右半边代价 right[5] = 0,相加得 4。最后一个也算好了。
完成 · answer = [11,8,5,4,3,4]：六个盒子的答案都填好了,answer = [11,8,5,4,3,4]。回看整套办法:不去为每个盒子从头加一遍,而是抓住相邻答案的差是左右两侧的球数,左扫一遍算 left、右扫一遍算 right,再逐位相加。总共只扫了三趟数组,线性时间就全部拿下。
边界:单盒且有球时答案 0;球全在别处时按距离逐个相加。都用同一套左右两遍累加处理,无需特判。
面试重点:answer[i] 是所有球到 i 的距离和;相邻答案差左右球数,拆左右两半各扫一遍前缀累加再相加,O(n);三语言只在收尾相加的写法上略有不同。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minOperations(self, boxes: str) -> List[int]: n = len(boxes) left = [0] * n right = [0] * n cnt = 0 for i in range(1, n): if boxes[i - 1] == '1': cnt += 1 left[i] = left[i - 1] + cnt cnt = 0 for i in range(n - 2, -1, -1): if boxes[i + 1] == '1': cnt += 1 right[i] = right[i + 1] + cnt return [a + b for a, b in zip(left, right)]复杂度
- 时间：O(n)，n 是盒子数。左扫一遍 n 次、右扫一遍 n 次、最后逐位相加又 n 次,总共三趟线性扫描,是 O(n)。相比之下,若对每个盒子都把所有球的距离从头加一遍,是两层循环 O(n^2),数据一大就慢。本题 n 最大 2000,线性做法轻松
- 空间：O(n)，按峰值算。额外开了 left、right 两个长度 n 的数组,还有输出数组 answer,都是 O(n)。若把 left 累加进结果、右遍时边扫边把 right 直接加到 answer 上,可以省掉一个数组,但量级仍是 O(n)(要交出去的 answer 本身就 O(n))。计数器 cnt 是常数
易错点
面试追问把动画讲成自己的话
追问这题的核心思路能一句话说清吗?
追问为什么要分左右两遍,不能一遍搞定吗?
追问三种语言实现上有差别吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
所有子字符串美丽值之和
LeetCode 1781 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题