How does the sliding window approach work for "Minimum Moves to Pick K Ones"?

The sliding window approach moves across the array, tracking the number of ones and changes needed within the window. It ensures that the optimal number of moves is calculated for each window size containing exactly k ones.

What is the cost of changing zeros into ones in this problem?

Each change of a zero into a one requires 2 moves, which must be carefully balanced with the number of ones already present in the array.

Can the solution be optimized using prefix sums?

Yes, prefix sums can be used to calculate the number of ones and zeros in any subarray, improving the efficiency of sliding window state updates.

What is the time complexity of the solution?

The time complexity is O(n) if using a sliding window approach with efficient state updates, where n is the length of the array.

How does the maxChanges value affect the solution?

maxChanges limits the number of zeros that can be converted into ones. The solution must efficiently balance the conversion of zeros with the number of moves to pick k ones.

#3086

Hard

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

拾起 K 个 1 需要的最少行动次数

给你一个下标从 0 开始的二进制数组 nums ，其长度为 n ；另给你一个正整数 k 以及一个非负整数 maxChanges 。 Alice 在玩一个游戏，游戏的目标是让 Alice 使用最少数量的行动次数从 nums 中拾起 k 个 1 。游戏开始时，Alice 可以选择数组 [0,…

数组贪心滑动窗口前缀和

题目描述

给你一个下标从 0 开始的二进制数组 nums，其长度为 n ；另给你一个 正整数 k 以及一个 非负整数 maxChanges 。

Alice 在玩一个游戏，游戏的目标是让 Alice 使用最少数量的行动次数从 nums 中拾起 k 个 1 。游戏开始时，Alice 可以选择数组 [0, n - 1] 范围内的任何索引 aliceIndex 站立。如果 nums[aliceIndex] == 1 ，Alice 会拾起一个 1 ，并且 nums[aliceIndex] 变成0（这不算作一次行动）。之后，Alice 可以执行 任意数量 的行动（包括零次），在每次行动中 Alice 必须恰好执行以下动作之一：

选择任意一个下标 j != aliceIndex 且满足 nums[j] == 0 ，然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。
选择任意两个相邻的下标 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

解释：如果游戏开始时 Alice 在 aliceIndex == 1 的位置上，按照以下步骤执行每个动作，他可以利用 3 次行动拾取 3 个 1 ：

游戏开始时 Alice 拾取了一个 1 ，nums[1] 变成了 0。此时 nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 j == 2 并执行第一种类型的动作。nums 变为 [1,0,1,0,0,1,1,0,0,1]
选择 x == 2 和 y == 1 ，并执行第二种类型的动作。nums 变为 [1,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 x == 0 和 y == 1 ，并执行第二种类型的动作。nums 变为 [0,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为 [0,0,0,0,0,1,1,0,0,1] 。

请注意，Alice 也可能执行其他的 3 次行动序列达成拾取 3 个 1 。

示例 2：

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

输出：4

解释：如果游戏开始时 Alice 在 aliceIndex == 0 的位置上，按照以下步骤执行每个动作，他可以利用 4 次行动拾取 2 个 1 ：

选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于 y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。
再次选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
再次选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。

提示：

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

lightbulb

解题思路

方法一：贪心 + 前缀和 + 二分查找

我们考虑枚举 Alice 的站立位置 $i$ ，对于每个 $i$ ，我们按照如下的策略进行操作：

首先，如果位置 $i$ 的数字为 $1$ ，我们可以直接拾取一个 $1$ ，不需要行动次数。
然后，我们对 $i$ 的左右两侧位置的数字 $1$ 进行拾取，执行的是行动 $2$ ，即把位置 $i-1$ 的 $1$ 移到位置 $i$ ，然后拾取；把位置 $i+1$ 的 $1$ 移到位置 $i$ ，然后拾取。每拾取一个 $1$ ，需要 $1$ 次行动。
接下来，我们最大限度地将 $i-1$ 或 $i+1$ 上的 $0$ ，利用行动 $1$ ，将其置为 $1$ ，然后利用行动 $2$ ，将其移动到位置 $i$ ，拾取。直到拾取的 $1$ 的数量达到 $k$ 或者行动 $1$ 的次数达到 $\textit{maxChanges}$ 。我们假设行动 $1$ 的次数为 $c$ ，那么总共需要 $2c$ 次行动。
利用完行动 $1$ ，如果拾取的 $1$ 的数量还没有达到 $k$ ，我们需要继续考虑在 $[1,..i-2]$ 和 $[i+2,..n]$ 的区间内，进行行动 $2$ ，将 $1$ 移动到位置 $i$ ，拾取。我们可以使用二分查找来确定这个区间的大小，使得拾取的 $1$ 的数量达到 $k$ 。具体地，我们二分枚举一个区间的大小 $d$ ，然后在区间 $[i-d,..i-2]$ 和 $[i+2,..i+d]$ 内，进行行动 $2$ ，将 $1$ 移动到位置 $i$ ，拾取。如果拾取的 $1$ 的数量达到 $k$ ，我们就更新答案。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

class Solution:
    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
        n = len(nums)
        cnt = [0] * (n + 1)
        s = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            cnt[i] = cnt[i - 1] + x
            s[i] = s[i - 1] + i * x
        ans = inf
        max = lambda x, y: x if x > y else y
        min = lambda x, y: x if x < y else y
        for i, x in enumerate(nums, 1):
            t = 0
            need = k - x
            for j in (i - 1, i + 1):
                if need > 0 and 1 <= j <= n and nums[j - 1] == 1:
                    need -= 1
                    t += 1
            c = min(need, maxChanges)
            need -= c
            t += c * 2
            if need <= 0:
                ans = min(ans, t)
                continue
            l, r = 2, max(i - 1, n - i)
            while l <= r:
                mid = (l + r) >> 1
                l1, r1 = max(1, i - mid), max(0, i - 2)
                l2, r2 = min(n + 1, i + 2), min(n, i + mid)
                c1 = cnt[r1] - cnt[l1 - 1]
                c2 = cnt[r2] - cnt[l2 - 1]
                if c1 + c2 >= need:
                    t1 = c1 * i - (s[r1] - s[l1 - 1])
                    t2 = s[r2] - s[l2 - 1] - c2 * i
                    ans = min(ans, t + t1 + t2)
                    r = mid - 1
                else:
                    l = mid + 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate efficiently manages the sliding window with updates to the running state.
question_mark
The candidate makes use of greedy techniques while keeping track of the number of moves.
question_mark
The candidate balances between the cost of making changes and moving within the window.

warning

常见陷阱

外企场景

error
Failing to update the state of the window correctly when sliding, especially when zeros are converted.
error
Not accounting for the cost of changing zeros into ones, which requires 2 moves per change.
error
Inefficiently recalculating subarrays or prefix sums, leading to higher time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling different values for k and maxChanges can lead to variations in the optimal solution and performance.
arrow_right_alt
Consider arrays with no zeros (all ones) or no ones (all zeros) for edge cases.
arrow_right_alt
Experimenting with larger arrays may require optimizations like prefix sum usage to avoid time limit exceeded errors.

help

常见问题

外企场景

继续练习

#3413 收集连续 K 个袋子可以获得的最多硬币数量 #2528 最大化城市的最小电量 #2271 毯子覆盖的最多白色砖块数