跳转至

3048. 标记所有下标的最早秒数 I

题目描述

给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。

一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。

从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：

  • 选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
  • 如果 nums[changeIndices[s]] 等于 0 ，标记 下标 changeIndices[s] 。
  • 什么也不做。

请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。

 

示例 1：

输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
输出：8
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
第 1 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [1,2,0] 。
第 2 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,2,0] 。
第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,1,0] 。
第 4 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,0,0] 。
第 5 秒，标​​​​​记 changeIndices[5] ，也就是标记下标 3 ，因为 nums[3] 等于 0 。
第 6 秒，标​​​​​记 changeIndices[6] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
第 7 秒，什么也不做。
第 8 秒，标记 changeIndices[8] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。
最早可以在第 8 秒标记所有下标。
所以答案是 8 。

示例 2：

输入：nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
输出：6
解释：这个例子中，我们总共有 7 秒。按照以下操作标记所有下标：
第 1 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,2] 。
第 2 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,1] 。
第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,0] 。
第 4 秒：标​​​​​记 changeIndices[4] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
第 5 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,0] 。
第 6 秒：标​​​​​记 changeIndices[6] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。
最早可以在第 6 秒标记所有下标。
所以答案是 6 。

示例 3：

Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: 这个例子中，无法标记所有下标，因为下标 1 不在 changeIndices 中。
所以答案是 -1 。

 

提示：

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 109
  • 1 <= m == changeIndices.length <= 2000
  • 1 <= changeIndices[i] <= n

解法

方法一：二分查找

思考

第 \(s\) 秒只能把 \(\textit{changeIndices}[s]\) 对应的值减一或标记（需已为 \(0\)）。\(n,m \le 2000\)。能在 \(t\) 秒完成则更长时间也能完成。

每个下标应尽量在其于前 \(t\) 秒中最后一次出现时再标记，以便把更早的秒用来减其它数。

对 \(t\) 二分：用最后出现时刻表模拟，非最后出现的秒当作一次减一额度；最后出现时额度必须够 \(nums[i]\)。

我们注意到，如果我们能够在 \(t\) 秒内标记所有下标，那么我们也能在 \(t' \geq t\) 秒内标记所有下标。因此，我们可以使用二分查找的方法找到最早的秒数。

我们定义二分查找的左右边界分别为 \(l = 1\) 和 \(r = m + 1\)，其中 \(m\) 是数组 changeIndices 的长度。对于每一个 \(t = \frac{l + r}{2}\)，我们检查是否能在 \(t\) 秒内标记所有下标。如果能，我们将右边界移动到 \(t\)，否则我们将左边界移动到 \(t + 1\)。最终，我们判定左边界是否大于 \(m\)，如果是则返回 \(-1\)，否则返回左边界。

题目的关键在于如何判断是否能在 \(t\) 秒内标记所有下标。我们可以使用一个数组 \(last\) 记录每一个下标最晚需要被标记的时间，用一个变量 \(decrement\) 记录当前可以减少的次数，用一个变量 \(marked\) 记录已经被标记的下标的数量。

我们遍历数组 changeIndices 的前 \(t\) 个元素，对于每一个元素 \(i\)，如果 \(last[i] = s\)，那么我们需要检查 \(decrement\) 是否大于等于 \(nums[i - 1]\)，如果是，我们将 \(decrement\) 减去 \(nums[i - 1]\)，并且将 \(marked\) 加一；否则，我们返回 False。如果 \(last[i] \neq s\)，那么我们可以暂时不标记下标，因此将 \(decrement\) 加一。最后，我们检查 \(marked\) 是否等于 \(n\)，如果是，我们返回 True，否则返回 False。

时间复杂度 \(O(m \times \log m)\)，空间复杂度 \(O(n)\)。其中 \(n\) 和 \(m\) 分别是数组 nums 和 changeIndices 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def earliestSecondToMarkIndices(
        self, nums: List[int], changeIndices: List[int]
    ) -> int:
        def check(t: int) -> bool:
            decrement = 0
            marked = 0
            last = {i: s for s, i in enumerate(changeIndices[:t])}
            for s, i in enumerate(changeIndices[:t]):
                if last[i] == s:
                    if decrement < nums[i - 1]:
                        return False
                    decrement -= nums[i - 1]
                    marked += 1
                else:
                    decrement += 1
            return marked == len(nums)

        m = len(changeIndices)
        l = bisect_left(range(1, m + 2), True, key=check) + 1
        return -1 if l > m else l

 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
41
42
class Solution {
    private int[] nums;
    private int[] changeIndices;

    public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
        this.nums = nums;
        this.changeIndices = changeIndices;
        int m = changeIndices.length;
        int l = 1, r = m + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l > m ? -1 : l;
    }

    private boolean check(int t) {
        int[] last = new int[nums.length + 1];
        for (int s = 0; s < t; ++s) {
            last[changeIndices[s]] = s;
        }
        int decrement = 0;
        int marked = 0;
        for (int s = 0; s < t; ++s) {
            int i = changeIndices[s];
            if (last[i] == s) {
                if (decrement < nums[i - 1]) {
                    return false;
                }
                decrement -= nums[i - 1];
                ++marked;
            } else {
                ++decrement;
            }
        }
        return marked == nums.length;
    }
}

 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
class Solution {
public:
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        int n = nums.size();
        int last[n + 1];
        auto check = [&](int t) {
            memset(last, 0, sizeof(last));
            for (int s = 0; s < t; ++s) {
                last[changeIndices[s]] = s;
            }
            int decrement = 0, marked = 0;
            for (int s = 0; s < t; ++s) {
                int i = changeIndices[s];
                if (last[i] == s) {
                    if (decrement < nums[i - 1]) {
                        return false;
                    }
                    decrement -= nums[i - 1];
                    ++marked;
                } else {
                    ++decrement;
                }
            }
            return marked == n;
        };

        int m = changeIndices.size();
        int l = 1, r = m + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l > m ? -1 : l;
    }
};

 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
func earliestSecondToMarkIndices(nums []int, changeIndices []int) int {
    n, m := len(nums), len(changeIndices)
    l := sort.Search(m+1, func(t int) bool {
        last := make([]int, n+1)
        for s, i := range changeIndices[:t] {
            last[i] = s
        }
        decrement, marked := 0, 0
        for s, i := range changeIndices[:t] {
            if last[i] == s {
                if decrement < nums[i-1] {
                    return false
                }
                decrement -= nums[i-1]
                marked++
            } else {
                decrement++
            }
        }
        return marked == n
    })
    if l > m {
        return -1
    }
    return l
}

 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
function earliestSecondToMarkIndices(nums: number[], changeIndices: number[]): number {
    const [n, m] = [nums.length, changeIndices.length];
    let [l, r] = [1, m + 1];
    const check = (t: number): boolean => {
        const last: number[] = Array(n + 1).fill(0);
        for (let s = 0; s < t; ++s) {
            last[changeIndices[s]] = s;
        }
        let [decrement, marked] = [0, 0];
        for (let s = 0; s < t; ++s) {
            const i = changeIndices[s];
            if (last[i] === s) {
                if (decrement < nums[i - 1]) {
                    return false;
                }
                decrement -= nums[i - 1];
                ++marked;
            } else {
                ++decrement;
            }
        }
        return marked === n;
    };
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l > m ? -1 : l;
}

评论