3776. 平衡循环数组的最小移动次数

Medium

题目描述

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

在一次移动中，一个人可以向其左邻居或右邻居转移恰好 1 个单位的余额。

返回使每个人都有非负余额所需的最少移动次数。如果不可能，返回 -1。

注意：保证最初最多只有 1 个索引的余额为负数。

示例 1：

输入：balance = [5,1,-4]
输出：4
解释：
一个最优的移动序列是：
- 从 i = 1 向 i = 2 转移 1 个单位，得到 balance = [5, 0, -3]
- 从 i = 0 向 i = 2 转移 1 个单位，得到 balance = [4, 0, -2]
- 从 i = 0 向 i = 2 转移 1 个单位，得到 balance = [3, 0, -1]
- 从 i = 0 向 i = 2 转移 1 个单位，得到 balance = [2, 0, 0]
因此，所需的最少移动次数是 4。

示例 2：

输入：balance = [1,2,-5,2]
输出：6

示例 3：

输入：balance = [-3,2]
输出：-1
解释：
对于 balance = [-3, 2]，不可能使所有余额都非负，所以答案是 -1。

约束：

1 <= n == balance.length <= 10^5
-10^9 <= balance[i] <= 10^9
最初 balance 中最多有一个负值

解题思路

这道题的关键是理解循环数组中的余额转移过程。

首先需要考虑特殊情况：

如果没有负数，直接返回 0
如果总和小于 0，说明正数余额不足以补充负数，返回 -1

对于一般情况，由于最多只有一个负数位置，我们需要将其他位置的正余额转移过来。在循环数组中，从位置 i 到位置 j 的最短距离有两种路径：顺时针和逆时针。

核心思路是贪心算法：

找到负数位置
按距离负数位置的远近对正数进行排序
贪心地选择距离最近的正数来补充负数

距离的计算需要考虑循环特性，从位置 i 到位置 j 的最短距离为： min((j - i + n) % n, (i - j + n) % n)

排序后，依次使用正数余额来补充负数，每次转移的代价就是距离乘以转移的单位数。需要注意的是，如果某个正数余额过大，可能只需要部分转移。

代码实现

class Solution {
public:
    long long minMoves(vector<int>& balance) {
        int n = balance.size();
        long long total = 0;
        int negIdx = -1;
        
        for (int i = 0; i < n; i++) {
            total += balance[i];
            if (balance[i] < 0) {
                negIdx = i;
            }
        }
        
        if (negIdx == -1) return 0;
        if (total < 0) return -1;
        
        vector<pair<int, int>> positive;
        for (int i = 0; i < n; i++) {
            if (balance[i] > 0) {
                int dist = min((i - negIdx + n) % n, (negIdx - i + n) % n);
                positive.push_back({dist, balance[i]});
            }
        }
        
        sort(positive.begin(), positive.end());
        
        long long moves = 0;
        long long need = -balance[negIdx];
        
        for (auto& p : positive) {
            int dist = p.first;
            int amount = p.second;
            
            long long use = min((long long)amount, need);
            moves += use * dist;
            need -= use;
            
            if (need == 0) break;
        }
        
        return moves;
    }
};

class Solution:
    def minMoves(self, balance: List[int]) -> int:
        n = len(balance)
        total = sum(balance)
        neg_idx = -1
        
        for i in range(n):
            if balance[i] < 0:
                neg_idx = i
                break
        
        if neg_idx == -1:
            return 0
        if total < 0:
            return -1
        
        positive = []
        for i in range(n):
            if balance[i] > 0:
                dist = min((i - neg_idx + n) % n, (neg_idx - i + n) % n)
                positive.append((dist, balance[i]))
        
        positive.sort()
        
        moves = 0
        need = -balance[neg_idx]
        
        for dist, amount in positive:
            use = min(amount, need)
            moves += use * dist
            need -= use
            
            if need == 0:
                break
        
        return moves

public class Solution {
    public long MinMoves(int[] balance) {
        int n = balance.Length;
        long total = 0;
        int negIdx = -1;
        
        for (int i = 0; i < n; i++) {
            total += balance[i];
            if (balance[i] < 0) {
                negIdx = i;
            }
        }
        
        if (negIdx == -1) return 0;
        if (total < 0) return -1;
        
        var positive = new List<(int dist, int amount)>();
        for (int i = 0; i < n; i++) {
            if (balance[i] > 0) {
                int dist = Math.Min((i - negIdx + n) % n, (negIdx - i + n) % n);
                positive.Add((dist, balance[i]));
            }
        }
        
        positive.Sort();
        
        long moves = 0;
        long need = -balance[negIdx];
        
        foreach (var (dist, amount) in positive) {
            long use = Math.Min(amount, need);
            moves += use * dist;
            need -= use;
            
            if (need == 0) break;
        }
        
        return moves;
    }
}

var minMoves = function(balance) {
    const n = balance.length;
    const total = balance.reduce((sum, val) => sum + val, 0);
    
    if (total < 0) return -1;
    
    let negIndex = -1;
    for (let i = 0; i < n; i++) {
        if (balance[i] < 0) {
            negIndex = i;
            break;
        }
    }
    
    if (negIndex === -1) return 0;
    
    const deficit = -balance[negIndex];
    let minMoves = Infinity;
    
    // Try going left
    let moves = 0;
    let collected = 0;
    for (let i = 1; i <= n - 1; i++) {
        const leftIdx = (negIndex - i + n) % n;
        const available = balance[leftIdx];
        const take = Math.min(available, deficit - collected);
        moves += take * i;
        collected += take;
        if (collected >= deficit) {
            minMoves = Math.min(minMoves, moves);
            break;
        }
    }
    
    // Try going right
    moves = 0;
    collected = 0;
    for (let i = 1; i <= n - 1; i++) {
        const rightIdx = (negIndex + i) % n;
        const available = balance[rightIdx];
        const take = Math.min(available, deficit - collected);
        moves += take * i;
        collected += take;
        if (collected >= deficit) {
            minMoves = Math.min(minMoves, moves);
            break;
        }
    }
    
    // Try both directions
    for (let leftDist = 1; leftDist < n; leftDist++) {
        let tempMoves = 0;
        let tempCollected = 0;
        
        // Collect from left
        for (let i = 1; i <= leftDist; i++) {
            const leftIdx = (negIndex - i + n) % n;
            const available = balance[leftIdx];
            const take = Math.min(available, deficit - tempCollected);
            tempMoves += take * i;
            tempCollected += take;
            if (tempCollected >= deficit) break;
        }
        
        if (tempCollected >= deficit) {
            minMoves = Math.min(minMoves, tempMoves);
            continue;
        }
        
        // Collect from right
        const remaining = deficit - tempCollected;
        for (let i = 1; i < n - leftDist; i++) {
            const rightIdx = (negIndex + i) % n;
            const available = balance[rightIdx];
            const take = Math.min(available, remaining - (tempCollected - (deficit - remaining)));
            if (take > 0) {
                tempMoves += take * i;
                tempCollected += take;
                if (tempCollected >= deficit) {
                    minMoves = Math.min(minMoves, tempMoves);
                    break;
                }
            }
        }
    }
    
    return minMoves === Infinity ? -1 : minMoves;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	时间复杂度	空间复杂度
时间	O(n log n)	O(n)
空间	O(n)	O(n)

时间复杂度主要来自对正数位置按距离排序的过程，空间复杂度来自存储正数位置和距离的数组。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析