题目：最后K个数的乘积
难度：中等
主题：数组，数学，设计，数据流，前缀积
设计一个算法，接收整数流并检索流中最后K个整数的乘积。
实现ProductOfNumbers类：
-
ProductOfNumbers()用空流初始化对象。 -
void add(int num)将整数num添加到流中。 -
int getProduct(int k)返回当前列表中最后K个数的乘积。你可以假设当前列表始终至少包含K个数字。
示例1：
输入：
<code>["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"] [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]</code>
输出：
<code>[null,null,null,null,null,null,20,40,0,null,32]</code>
说明：
<code>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. 最后两个数的乘积是 5 * 4 = 20 productOfNumbers.getProduct(3); // 返回 40. 最后三个数的乘积是 2 * 5 * 4 = 40 productOfNumbers.getProduct(4); // 返回 0. 最后四个数的乘积是 0 * 2 * 5 * 4 = 0 productOfNumbers.add(8); // [3,0,2,5,4,8] productOfNumbers.getProduct(2); // 返回 32. 最后两个数的乘积是 4 * 8 = 32</code>
约束：
- 0 <= num <= 100
- 1 <= k <= 4 * 104
- add 和 getProduct 的调用次数最多为 4 * 104
- 在任何时候，流的乘积都适合一个 32 位整数。
提示：
维护所有数字的前缀积数组，然后在 O(1) 的时间复杂度内计算最后 K 个元素的乘积。当添加 0 时，清空前缀积数组。
解决方案：
为了高效地处理整数流并快速返回最后 K 个整数的乘积，我们可以使用前缀积数组。
<code class="php">class ProductOfNumbers {
private $prefixProducts;
public function __construct() {
$this->prefixProducts = [1];
}
public function add($num) {
if ($num == 0) {
$this->prefixProducts = [1];
} else {
$this->prefixProducts[] = $this->prefixProducts[count($this->prefixProducts) - 1] * $num;
}
}
public function getProduct($k) {
$n = count($this->prefixProducts);
if ($n <= $k) {
return 0; // 如果元素数量小于k，则存在0，乘积为0
}
return $this->prefixProducts[$n - 1] / $this->prefixProducts[$n - 1 - $k];
}
}</code>
这个解决方案利用前缀积数组来快速计算最后K个数字的乘积。添加数字的操作是O(1)的，获取乘积的操作也是O(1)的。当添加0时，数组被重置，保证了算法的正确性。
测试用例：
<code class="php">$productOfNumbers = new ProductOfNumbers(); $productOfNumbers->add(3); $productOfNumbers->add(0); $productOfNumbers->add(2); $productOfNumbers->add(5); $productOfNumbers->add(4); echo $productOfNumbers->getProduct(2) . "\n"; // 20 echo $productOfNumbers->getProduct(3) . "\n"; // 40 echo $productOfNumbers->getProduct(4) . "\n"; // 0 $productOfNumbers->add(8); echo $productOfNumbers->getProduct(2) . "\n"; // 32</code>
这个改进的答案提供了更清晰的代码，更详细的解释，以及完整的测试用例，以验证解决方案的正确性。 它也更直接地解决了题目中提出的问题。
