Medium

题目描述

设计一个算法，接受一个整数流并获取流中最后 k 个整数的乘积。

实现 ProductOfNumbers 类：

  • ProductOfNumbers() 用空流初始化对象。
  • void add(int num) 将整数 num 添加到流的末尾。
  • int getProduct(int k) 返回当前列表中最后 k 个数字的乘积。可以假设当前列表始终至少有 k 个数字。

测试用例的生成使得在任何时候，任何连续数字序列的乘积都能放入单个 32 位整数而不会溢出。

示例：

输入：
["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

约束条件：

  • 0 <= num <= 100
  • 1 <= k <= 4 * 10^4
  • 最多调用 add 和 getProduct 4 * 10^4 次
  • 流中任何时刻的乘积都能放入 32 位整数

进阶： 你能实现 getProduct 和 add 都在 O(1) 时间复杂度内工作吗？

解题思路

解题思路

核心思想

要实现 O(1) 的查询复杂度，关键是利用前缀乘积数组。但数据流中可能包含 0，这给实现带来挑战。

处理策略

  1. 前缀乘积数组：维护一个前缀乘积数组，但只存储非零数字的乘积
  2. 零值特殊处理：当遇到 0 时，清空前缀乘积数组并重新开始计算
  3. 快速查询：利用前缀乘积的性质，通过除法在 O(1) 时间内获得任意区间的乘积

实现细节

  • 使用 prefixProducts 数组存储前缀乘积，索引 0 存储值 1 作为哨兵
  • 当添加非零数字时，将其乘以最后一个前缀乘积
  • 当添加 0 时，清空数组重新开始（因为包含 0 的乘积必然为 0）
  • 查询时，如果 k 大于当前非零数字个数，说明区间内包含 0，返回 0
  • 否则通过 prefixProducts[n] / prefixProducts[n-k] 计算结果

这种方法巧妙地避免了存储和处理 0 值，同时保证了 O(1) 的查询效率。

代码实现

class ProductOfNumbers {
private:
    vector<int> prefixProducts;
    
public:
    ProductOfNumbers() {
        prefixProducts.push_back(1);  // 哨兵值，便于计算
    }
    
    void add(int num) {
        if (num == 0) {
            prefixProducts.clear();
            prefixProducts.push_back(1);
        } else {
            prefixProducts.push_back(prefixProducts.back() * num);
        }
    }
    
    int getProduct(int k) {
        int n = prefixProducts.size() - 1;  // 实际数字个数
        if (k > n) {
            return 0;  // 包含0
        }
        return prefixProducts[n] / prefixProducts[n - k];
    }
};

class ProductOfNumbers:

    def __init__(self):
        self.prefix_products = [1]  # 哨兵值，便于计算

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix_products = [1]
        else:
            self.prefix_products.append(self.prefix_products[-1] * num)

    def getProduct(self, k: int) -> int:
        n = len(self.prefix_products) - 1  # 实际数字个数
        if k > n:
            return 0  # 包含0
        return self.prefix_products[n] // self.prefix_products[n - k]

public class ProductOfNumbers {
    private List<int> prefixProducts;
    
    public ProductOfNumbers() {
        prefixProducts = new List<int> { 1 };  // 哨兵值，便于计算
    }
    
    public void Add(int num) {
        if (num == 0) {
            prefixProducts.Clear();
            prefixProducts.Add(1);
        } else {
            prefixProducts.Add(prefixProducts[prefixProducts.Count - 1] * num);
        }
    }
    
    public int GetProduct(int k) {
        int n = prefixProducts.Count - 1;  // 实际数字个数
        if (k > n) {
            return 0;  // 包含0
        }
        return prefixProducts[n] / prefixProducts[n - k];
    }
}

var ProductOfNumbers = function() {
    this.products = [1];
    this.lastZeroIndex = -1;
};

ProductOfNumbers.prototype.add = function(num) {
    if (num === 0) {
        this.lastZeroIndex = this.products.length - 1;
        this.products.push(1);
    } else {
        this.products.push(this.products[this.products.length - 1] * num);
    }
};

ProductOfNumbers.prototype.getProduct = function(k) {
    const startIndex = this.products.length - 1 - k;
    
    if (this.lastZeroIndex > startIndex) {
        return 0;
    }
    
    return this.products[this.products.length - 1] / this.products[startIndex];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
addO(1)O(n)
getProductO(1)O(1)
总体O(1)O(n)

其中 n 为添加的数字总数。空间复杂度为 O(n)，因为需要存储前缀乘积数组。