1769. 移动所有球到每个盒子所需的最小操作数

🟠   🔖  数组 字符串 前缀和  🔗 力扣 LeetCode

题目

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty , and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"

Output: [1,1,3]

Explanation: The answer for each box is as follows:

1. First box: you will have to move one ball from the second box to the first box in one operation.

2. Second box: you will have to move one ball from the first box to the second box in one operation.

3. Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"

Output: [11,8,5,4,3,4]

Constraints:

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] is either '0' or '1'.

题目大意

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

示例 1：

输入： boxes = "110"

输出：[1,1,3]

解释： 每个盒子对应的最小操作数如下：

1. 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。

2. 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。

3. 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入： boxes = "001011"

输出：[11,8,5,4,3,4]

提示：

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] 为 '0' 或 '1'

解题思路

题目要求计算将所有球移动到每个盒子所需的操作数。可以用更高效的前缀和解法替代暴力求解，通过一次从左到右的遍历，以及一次从右到左的遍历，累积计算所需操作数。

• 每个盒子 i 的操作数可以看作是左侧盒子和右侧盒子的独立贡献之和：
  • 左侧盒子贡献：将左侧球移动到当前盒子所需的操作数。
  • 右侧盒子贡献：将右侧球移动到当前盒子所需的操作数。

通过维护累积的球数量和操作数，在两次遍历中动态更新这两部分贡献值。

1. 从左到右遍历

• 用两个变量 leftBalls 和 leftMoves：
  • leftBalls 表示左侧的球数量。
  • leftMoves 表示将所有左侧球移动到当前盒子的操作数。
• 遍历过程中：
  • 当前盒子的操作数增加 leftMoves。
  • 更新 leftBalls，如果当前盒子有球，则 leftBalls += 1。
  • 将 leftBalls 累加到 leftMoves，因为每个左侧球向右移动一格都会增加操作数。

2. 从右到左遍历

• 用两个变量 rightBalls 和 rightMoves：
  • rightBalls 表示右侧的球数量。
  • rightMoves 表示将所有右侧球移动到当前盒子的操作数。
• 遍历过程中：
  • 当前盒子的操作数增加 rightMoves。
  • 更新 rightBalls，如果当前盒子有球，则 rightBalls += 1。
  • 将 rightBalls 累加到 rightMoves，因为每个右侧球向左移动一格都会增加操作数。

复杂度分析

• 时间复杂度：O(n)，两次线性遍历（从左到右和从右到左）。
• 空间复杂度：O(n)，结果数组需要额外的存储空间。

代码

/**
 * @param {string} boxes
 * @return {number[]}
 */
var minOperations = function (boxes) {
	const n = boxes.length;
	let res = new Array(n).fill(0);

	let leftBalls = 0; // 表示左侧的球数量
	let leftMoves = 0; // 表示将左侧球移动到当前盒子的操作数
	for (let i = 0; i < n; i++) {
		res[i] += leftMoves; // 累加左侧的操作数到当前盒子
		leftBalls += Number(boxes[i]); // 如果当前盒子有球，则更新左侧球数量
		leftMoves += leftBalls; // 累加左侧球的操作数
	}

	let rightBalls = 0; // 表示右侧的球数量
	let rightMoves = 0; // 表示将右侧球移动到当前盒子的操作数
	for (let i = n - 1; i >= 0; i--) {
		res[i] += rightMoves; // 累加右侧的操作数到当前盒子
		rightBalls += Number(boxes[i]); // 如果当前盒子有球，则更新右侧球数量
		rightMoves += rightBalls; // 累加右侧球的操作数
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1217	玩筹码	[✓]	贪心 数组 数学	🟢	🀄️ 🔗
2850	将石头分散到网格图的最少移动次数		广度优先搜索 数组 动态规划 1+	🟠	🀄️ 🔗