Hard

题目描述

给你一个长度为 n 的二进制数组 nums，一个正整数 k 和一个非负整数 maxChanges。

Alice 玩一个游戏，目标是用最少的移动次数从 nums 中收集 k 个 1。游戏开始时，Alice 选择范围 [0, n - 1] 内的任意索引 aliceIndex 并站在那里。如果 nums[aliceIndex] == 1，Alice 收集这个 1 并且 nums[aliceIndex] 变为 0（这不算作一次移动）。之后，Alice 可以进行任意次数（包括零次）的移动，每次移动必须执行以下操作之一：

  1. 选择任意索引 j != aliceIndex 使得 nums[j] == 0，并设置 nums[j] = 1。此操作最多可以执行 maxChanges 次。
  2. 选择任意两个相邻的索引 x 和 y（|x - y| == 1）使得 nums[x] == 1，nums[y] == 0，然后交换它们的值（设置 nums[y] = 1 和 nums[x] = 0）。如果 y == aliceIndex，Alice 在此移动后收集这个 1 并且 nums[y] 变为 0。

返回 Alice 收集恰好 k 个 1 所需的最少移动次数。

示例 1：

输入：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1
输出：3

示例 2：

输入：nums = [0,0,0,0], k = 2, maxChanges = 3
输出：4

约束：

  • 2 <= n <= 10^5
  • 0 <= nums[i] <= 1
  • 1 <= k <= 10^5
  • 0 <= maxChanges <= 10^5
  • maxChanges + sum(nums) >= k

解题思路

这道题需要综合考虑两种获取 1 的方式：直接移动现有的 1 和通过 change 操作创建新的 1。

核心思路：

  1. 成本分析：

    • 通过 change 操作获取 1 需要 2 步（创建 + 移动到当前位置）
    • 移动现有的 1 到当前位置需要的步数等于距离

  2. 策略选择：

    • 对于距离较近的 1，直接移动比较划算
    • 对于距离较远的 1，使用 change 操作更优
    • 关键在于找到最优的分界点

  3. 算法步骤：

    • 首先提取所有 1 的位置
    • 枚举所有可能的 Alice 起始位置
    • 对于每个位置，计算收集 k 个 1 的最小成本：
      • 考虑当前位置本身是否有 1
      • 使用滑动窗口找到距离最近的若干个 1
      • 其余用 change 操作补充

  4. 优化技巧：

    • 使用前缀和快速计算区间内 1 的移动成本
    • 滑动窗口维护最小成本的连续 1 的子集

推荐解法：使用滑动窗口 + 前缀和的贪心算法，时间复杂度最优。

代码实现

class Solution {
public:
    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
        vector<int> ones;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                ones.push_back(i);
            }
        }
        
        if (ones.empty()) {
            return 2LL * k;
        }
        
        int n = ones.size();
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + ones[i];
        }
        
        long long ans = LLONG_MAX;
        
        for (int i = 0; i < nums.size(); i++) {
            int collect = nums[i];
            long long cost = 0;
            
            int need = k - collect;
            int use_change = min(need, maxChanges);
            need -= use_change;
            cost += 2LL * use_change;
            
            if (need == 0) {
                ans = min(ans, cost);
                continue;
            }
            
            long long min_move_cost = LLONG_MAX;
            
            for (int len = need; len <= n; len++) {
                for (int l = 0; l + len - 1 < n; l++) {
                    int r = l + len - 1;
                    int mid = l + len / 2;
                    
                    long long move_cost = 0;
                    long long left_sum = prefix[mid] - prefix[l];
                    long long right_sum = prefix[r + 1] - prefix[mid + 1];
                    
                    move_cost += (long long)ones[mid] * (mid - l) - left_sum;
                    move_cost += right_sum - (long long)ones[mid] * (r - mid);
                    
                    min_move_cost = min(min_move_cost, move_cost);
                }
            }
            
            ans = min(ans, cost + min_move_cost);
        }
        
        return ans;
    }
};

class Solution:
    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
        ones = [i for i, x in enumerate(nums) if x == 1]
        
        if not ones:
            return 2 * k
        
        n = len(ones)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + ones[i]
        
        ans = float('inf')
        
        for i in range(len(nums)):
            collect = nums[i]
            cost = 0
            
            need = k - collect
            use_change = min(need, maxChanges)
            need -= use_change
            cost += 2 * use_change
            
            if need == 0:
                ans = min(ans, cost)
                continue
            
            min_move_cost = float('inf')
            
            for length in range(need, n + 1):
                for l in range(n - length + 1):
                    r = l + length - 1
                    mid = l + length // 2
                    
                    move_cost = 0
                    left_sum = prefix[mid] - prefix[l]
                    right_sum = prefix[r + 1] - prefix[mid + 1]
                    
                    move_cost += ones[mid] * (mid - l) - left_sum
                    move_cost += right_sum - ones[mid] * (r - mid)
                    
                    min_move_cost = min(min_move_cost, move_cost)
            
            ans = min(ans, cost + min_move_cost)
        
        return ans

public class Solution {
    public long MinimumMoves(int[] nums, int k, int maxChanges) {
        List<int> ones = new List<int>();
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 1) {
                ones.Add(i);
            }
        }
        
        if (ones.Count == 0) {
            return 2L * k;
        }
        
        int n = ones.Count;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + ones[i];
        }
        
        long ans = long.MaxValue;
        
        for (int i = 0; i < nums.Length; i++) {
            int collect = nums[i];
            long cost = 0;
            
            int need = k - collect;
            int useChange = Math.Min(need, maxChanges);
            need -= useChange;
            cost += 2L * useChange;
            
            if (need == 0) {
                ans = Math.Min(ans, cost);
                continue;
            }
            
            long minMoveCost = long.MaxValue;
            
            for (int len = need; len <= n; len++) {
                for (int l = 0; l + len - 1 < n; l++) {
                    int r = l + len - 1;
                    int mid = l + len / 2;
                    
                    long moveCost = 0;
                    long leftSum = prefix[mid] - prefix[l];
                    long rightSum = prefix[r + 1] - prefix[mid + 1];
                    
                    moveCost += (long)ones[mid] * (mid - l) - leftSum;
                    moveCost += rightSum - (long)ones[mid] * (r - mid);
                    
                    minMoveCost = Math.Min(minMoveCost, moveCost);
                }
            }
            
            ans = Math.Min(ans, cost + minMoveCost);
        }
        
        return ans;
    }
}

var minimumMoves = function(nums, k, maxChanges) {
    const ones = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² × m)，其中 n 是数组长度，m 是 1 的个数
空间复杂度O(m)，用于存储 1 的位置和前缀和数组

相关题目