题目描述

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

1. add(int num)
   • 将数字 num 添加到当前数字列表的最后面。
2. 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

限制

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

算法

(暴力) 插入 $O(1)$，查询 $O(1)$

1. 维护一个数组记录当前非 0 数字的前缀积，由于题目保证了不会溢出，所以可以直接暴力算。初始时插入一个 1。
2. 插入时，如果遇到了一个非 0 数字，则计算前缀积插入数组。否则，清空数组并插入一个 1。
3. 查询时，如果当前数组元素的个数大于 k，则返回 nums.back() / nums[nums.size() - k - 1]，否则返回 0。

时间复杂度

• 每种操作的时间复杂度都是常数。

空间复杂度

• 需要额外 $O(n)$ 的空间记录前缀积。

C++ 代码

class ProductOfNumbers {
public:
    vector<int> nums;

    ProductOfNumbers() {
        nums.push_back(1);
    }

    void add(int num) {
        if (num == 0) {
            nums.clear();
            nums.push_back(1);
        } else {
            nums.push_back(num * nums.back());
        }
    }

    int getProduct(int k) {
        if (nums.size() > k)
            return nums.back() / nums[nums.size() - k - 1];

        return 0;
    }
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */