跳转至

4004. 使循环数组余额非负的最少移动次数 II 🔒

题目描述

给定一个长度为 n 的 环形数组 balance，其中 balance[i] 是第 i 个人的净余额。

在一次操作中，一个人可以向其左侧或右侧的相邻人员转移 恰好 1 单位的余额。

返回使每个人的余额都变为 非负 所需的 最少 操作次数。如果无法做到，则返回 -1。

 

示例 1：

输入：balance = [-1,2,-1]

输出：2

解释：

一种最优的操作序列如下：

  • 从 i = 1 向 i = 0 转移 1 单位余额，得到 balance = [0, 1, -1]
  • 从 i = 1 向 i = 2 转移 1 单位余额，得到 balance = [0, 0, 0]

因此，所需的最少操作次数为 2。

示例 2：

输入：balance = [4,-1,-2]

输出：3

解释：

一种最优的操作序列如下：

  • 从 i = 0 向 i = 1 转移 1 单位余额，得到 balance = [3, 0, -2]
  • 从 i = 0 向 i = 2 转移 1 单位余额，得到 balance = [2, 0, -1]
  • 从 i = 0 向 i = 2 再转移 1 单位余额，得到 balance = [1, 0, 0]

因此，所需的最少操作次数为 3。

示例 3：

输入：balance = [-3,-3,5]

输出：-1

解释：

对于 balance = [-3, -3, 5]，无法使所有人的余额都变为非负，因此答案为 -1。

 

提示：

  • 1 <= n == balance.length <= 1000
  • -105 <= balance[i] <= 105

解法

方法一

1


1


1


1

评论