1352. 最后 K 个数的乘积

🟠   🔖  设计 队列 数组 数学 数据流  🔗 力扣 LeetCode

题目

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.

Implement the ProductOfNumbers class:

• ProductOfNumbers() Initializes the object with an empty stream.
• void add(int num) Appends the integer num to the stream.
• int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.

The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:

Input

["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]

[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output

[null,null,null,null,null,null,20,40,0,null,32]

Explanation

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); // return 20. The product of the last 2 numbers is 5 \* 4 = 20

productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 \* 5 \* 4 = 40

productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 \* 2 \* 5 \* 4 = 0

productOfNumbers.add(8); // [3,0,2,5,4,8]

productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 \* 8 = 32

Constraints:

• 0 <= num <= 100
• 1 <= k <= 4 * 10^4
• At most 4 * 10^4 calls will be made to add and getProduct.
• The product of the stream at any point in time will fit in a 32-bit integer.

题目大意

请你实现一个「数字乘积类」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

解题思路

1. 使用前缀乘积（Prefix Product）优化计算：

   • 维护一个 arr 数组，其中 arr[i] 存储的是前 i 个数字的累积乘积（prefix product）。
   • 这样，在查询最后 k 个数的乘积时，可以直接用 除法 计算： getProduct(k) = arr[size]/arr[size - k] 这一技巧可以 O(1) 计算乘积，避免暴力遍历计算，提升查询效率。

2. 处理 0 的情况：

   • 由于除法不适用于 0，需要特殊处理。当遇到 num == 0 时，数组 arr 需要重置为 [1]，并将 size 设为 0，相当于清空之前的记录。
   • 这是因为 0 会破坏前缀乘积的连贯性（0 乘任何数都为 0），因此之前的所有计算结果都不再有效。

复杂度分析

• add(num) 操作:

  • 时间复杂度： O(1)，因为只需要在 arr 末尾追加一个元素。
  • 空间复杂度： O(n)，n 是调用 add() 的次数。

• getProduct(k) 操作:

  • 时间复杂度： O(1)，因为计算乘积只需一次除法运算。
  • 空间复杂度： O(1)，因为不会使用额外的存储空间。

代码

var ProductOfNumbers = function () {
	this.arr = [1];
	this.size = 0;
};

/**
 * @param {number} num
 * @return {void}
 */
ProductOfNumbers.prototype.add = function (num) {
	if (num == 0) {
		this.arr = [1];
		this.size = 0;
	} else {
		this.arr.push(this.arr[this.size] * num);
		this.size++;
	}
};

/**
 * @param {number} k
 * @return {number}
 */
ProductOfNumbers.prototype.getProduct = function (k) {
	if (k > this.size) return 0;
	return this.arr[this.size] / this.arr[this.size - k];
};