题目描述
思路解析动画文字版
记牢:目标右移一格,左边每个球多走一步、右边每个球少走一步。左遍 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题