LC 1894. 找到需要补充粉笔的学生编号

题目描述

这是 LeetCode 上的 1894. 找到需要补充粉笔的学生编号 ，难度为 中等。

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：chalk = [5,1,5], k = 22

输出：0

解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。
- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。
- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。
- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。
编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。

示例 2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：chalk = [3,4,1,2], k = 25

输出：1

解释：学生消耗粉笔情况如下：
- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。
- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。
- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。
- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。
- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。
编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。

提示：

  • chalk.length == n
  • 1 <= n <= $10^5$
  • 1 <= chalk[i] <= $10^5$
  • 1 <= k <= $10^9$

前缀和 + 二分

根据题意，每个学生消耗的粉笔为定值，所有粉笔最终会像老师的教导一样孜孜不倦地循环投入在所有的学生身上。

因此我们可以预处理出前缀和数组 $sum$，将 $k$ 对所有学生一次循环所消耗总粉笔数（$sum[n]$）进行取模，得到最后一轮开始前的粉笔数量。

然后对前缀和数组进行二分，找到最后一位满足粉笔要求的学生，其往后一位的同学编号即是答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + chalk[i - 1];
        k = (int)(k % sum[n]);
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (sum[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return sum[r] <= k ? r : r - 1;
    }
}

  • 时间复杂度：预处理前缀和的复杂度为 $O(n)$；二分求答案的复杂度为 $O(\log{n})$。整体复杂度为 $O(n)$
  • 空间复杂度：$O(n)$

模拟

通过解法一，我们发现复杂度的上界为预处理前缀和的复杂度 $O(n)$，同时「对单次循环消耗的总粉笔数取模操作」确保了剩余的粉笔数必然会在单次遍历中消耗完成。

因此 $O(\log{n})$ 的二分其实是没有必要的，只需要再对 chalk 进行最后一轮的遍历模拟即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long max = 0;
        for (int i : chalk) max += i;
        k = (int)(k % max);
        for (int i = 0; i < n; i++) {
            k -= chalk[i];
            if (k < 0) return i;
        }
        return -1; // never
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1894 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。