移动所有球到每个盒子所需的最小操作数 图解题解

每个盒子的 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。

Python

from __future__ import annotations
from 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)]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        int left[n];
        int right[n];
        memset(left, 0, sizeof left);
        memset(right, 0, sizeof right);
        for (int i = 1, cnt = 0; i < n; ++i) {
            cnt += boxes[i - 1] == '1';
            left[i] = left[i - 1] + cnt;
        }
        for (int i = n - 2, cnt = 0; ~i; --i) {
            cnt += boxes[i + 1] == '1';
            right[i] = right[i + 1] + cnt;
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) ans[i] = left[i] + right[i];
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1, cnt = 0; i < n; ++i) {
            if (boxes.charAt(i - 1) == '1') {
                ++cnt;
            }
            left[i] = left[i - 1] + cnt;
        }
        for (int i = n - 2, cnt = 0; i >= 0; --i) {
            if (boxes.charAt(i + 1) == '1') {
                ++cnt;
            }
            right[i] = right[i + 1] + cnt;
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = left[i] + right[i];
        }
        return ans;
    }
}