盒子中小球的最大数量

难度: Easy

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

示例 1：

输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球，小球数量为 2 。

示例 2：

输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。

示例 3：

输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球，小球数量为 2 。

提示：

1 <= lowLimit <= highLimit <= 10⁵

Submission

运行时间: 68 ms

内存: 16.5 MB

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        ans = 0
        lst = [0]*(9*6)
        for i in range(lowLimit,highLimit+1):
            suma = 0
            while i != 0:
                suma += i % 10
                i = i // 10
            lst[suma] += 1
        return max(lst)

Explain

这个题解的核心思路是使用一个数组来记录每个盒子中小球的数量。首先，创建一个足够大的数组 `lst` 来存储每个可能的盒子编号对应的小球数。数组的大小是 `9*6=54`，因为最大的小球编号为999999，其数字和为54。对于每个小球编号从 `lowLimit` 到 `highLimit`，计算其每位数字之和，这个和就是小球应当放入的盒子的编号。然后将对应盒子的计数增加。最后，从数组 `lst` 中找到计数最大的盒子，返回这个最大值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countBalls(self, lowLimit: int, highLimit: int) -> int:
        # 初始化最大数量为0
        ans = 0
        # 初始化一个长度为54的数组，用于记录每个盒子的小球数量
        lst = [0]*(9*6)
        # 遍历每个小球的编号
        for i in range(lowLimit,highLimit+1):
            suma = 0
            # 计算当前编号i的各位数字之和
            while i != 0:
                suma += i % 10
                i = i // 10
            # 将编号为suma的盒子中的小球数量加1
            lst[suma] += 1
        # 返回数组中的最大值，即某个盒子中小球数量的最大值
        return max(lst)

Explore

数组大小为54是基于数字和的最大可能值。对于任何六位数（如最大的小球编号999999），其最大可能的数字和是每位上的最大数字9相加，即9+9+9+9+9+9=54。因此，为了确保能够记录从最小的数字和1到最大的数字和54的每个盒子中的小球数量，需要一个大小至少为54的数组。

在题解中，变量i在计算数字和的过程中被修改，这确实会影响下一次迭代。为了解决这个问题，并避免对循环控制变量i的修改，应使用另一个变量来保存i的值用于计算数字和。例如，可以定义一个新变量current，设置为current = i，然后使用current进行数字和的计算，这样就不会影响i的值，保证循环能正确迭代。

是的，数组lst初始化为长度54是基于所有小球编号的最大数字和不会超过54这一事实。这是因为即使是最大的小球编号999999，其数字和也只有54。如果存在一个理论上的小球编号，使得其数字和超过54，那么这将导致数组越界访问错误，因为我们的数组只为数字和1到54的盒子分配了空间。但根据题目条件，这种情况不会发生。