最后 K 个数的乘积

标签: 设计队列数组数学数据流

难度: Medium

请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：

1. add(int num)

将数字 num 添加到当前数字列表的最后面。

2. getProduct(int k)

返回当前数字列表中，最后 k 个数字的乘积。
你可以假设当前列表中始终至少包含 k 个数字。

题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。

示例：

输入：
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

输出：
[null,null,null,null,null,null,20,40,0,null,32]

解释：
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32

提示：

add 和 getProduct 两种操作加起来总共不会超过 40000 次。
0 <= num <= 100
1 <= k <= 40000

Submission

运行时间: 126 ms

内存: 29.5 MB

class ProductOfNumbers:

    def __init__(self):
        self.nums = [1]  # 初始化一个包含1的列表，用于计算乘积

    def add(self, num: int) -> None:
        if num == 0:
            self.nums = [1]  # 如果遇到0，则重新开始计算乘积，将列表重置为只包含1
        else:
            self.nums.append(self.nums[-1] * num)  # 否则，将当前数字与列表中最后一个数字的乘积添加到列表中

    def getProduct(self, k: int) -> int:
        if k >= len(self.nums):
            return 0  # 如果k大于等于列表长度，说明列表中存在0，直接返回0
        else:
            return self.nums[-1] // self.nums[-k-1]  # 返回列表中最后k个数字的乘积，通过整除运算得到结果

class ProductOfNumbers:

    def __init__(self):
        self.prefix = [1]  # 初始化辅助数组，用于保存当前位置之前所有数字的乘积

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix = [1]  # 如果遇到0，则重置辅助数组为只包含一个元素1
        else:
            self.prefix.append(self.prefix[-1] * num)  # 否则，将当前数字与辅助数组中最后一个元素的乘积添加到辅助数组中

    def getProduct(self, k: int) -> int:
        if k >= len(self.prefix):
            return 0  # 如果k大于等于辅助数组长度，说明辅助数组中存在0（实际上不会存在0，但为了保持逻辑一致性，这里进行特判）
        else:
            return self.prefix[-1] // self.prefix[-k-1]  # 返回辅助数组中最后k个元素的乘积（通过相除的方式得到结果）

Explain

这个题解使用了前缀乘积数组来快速计算指定范围内数字的乘积。通过维护一个数组，每个元素存储从列表开始到当前位置的所有数字的乘积。当添加一个新数字时，若数字为0，则重置数组因为任何数乘以0都是0，这相当于重新开始一段新的序列；若非0，则将其乘以前缀数组的最后一个元素（即当前所有元素的乘积）并追加到数组末尾。对于查询操作，利用前缀乘积，通过最后一个元素除以第len(prefix)-k-1个元素的结果来获得最后k个元素的乘积。若k等于或大于数组长度，意味着中间出现了0，因此返回0。

时间复杂度: O(1)

空间复杂度: O(n)


class ProductOfNumbers:

    def __init__(self):
        self.prefix = [1]  # 初始化前缀乘积数组，从1开始，便于计算

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix = [1]  # 遇到0时重置数组，因为0将使任何后续乘积为0
        else:
            self.prefix.append(self.prefix[-1] * num)  # 更新前缀乘积数组，添加当前元素的乘积

    def getProduct(self, k: int) -> int:
        if k >= len(self.prefix):
            return 0  # 如果请求的产品长度超过数组长度，返回0（因存在0的影响）
        else:
            return self.prefix[-1] // self.prefix[-k-1]  # 通过前缀乘积，计算最后k个数的乘积

Explore

在`ProductOfNumbers`的实现中，每当`add`方法接收到0作为输入时，前缀乘积数组会被重置为只包含一个元素1。这是因为0的存在使得之后所有的乘积结果都将为0，直到再次添加非零元素。因此，无论添加多少个连续的0，前缀数组都将维持在这个重置状态。在此状态下执行`getProduct`查询，如果`k`不为0，则查询结果将是0，因为它试图获取包含0的段的乘积。

在`add`方法中遇到0后不简单地添加一个0到前缀乘积数组，而是重置数组，是因为添加0将使得该点之后所有计算的乘积结果均为0，失去了维持前缀乘积的意义。通过重置数组并开始一个新的乘积序列，可以避免在执行`getProduct`查询时不必要的误导和性能损耗。这种处理方式简化了逻辑，保证了乘积的正确计算。

当`k`的值等于前缀乘积数组的长度时，表示需要获取的乘积涵盖了整个数组的范围，其中包括初始化时的那个1。在这种情况下，如果数组长度等于`k`，则意味着在这个范围内存在至少一个0（因为只有遇到0才会重置数组），导致所有产品均为0。因此，按照实现逻辑，如果`k`等于或超过数组长度，将直接返回0。

前缀乘积数组从1开始初始化，是因为1是乘法的单位元素，即任何数字乘以1都不改变其值。这样做可以简化乘积的计算过程，使得在添加第一个元素时可以直接乘以1，得到该元素本身。如果从0开始，那么任何后续乘积都会变为0，而从其他数字开始则会错误地改变乘积的值。因此，从1开始是保证乘积正确性和计算简便性的最佳选择。