How do you handle zeros in the Product of the Last K Numbers problem?

Track zero positions in the stream and return zero for any getProduct query if a zero exists within the last k elements.

Can getProduct run faster than O(k) in this problem?

Yes, using prefix products and zero tracking, getProduct runs in O(1) without scanning the last k elements.

What happens if k is larger than the current number of elements?

Return the product of all available elements or zero if any zero exists within that range, ensuring correctness.

Why use an array of prefix products instead of recomputing each query?

It allows constant-time product calculation while efficiently handling zeros, preventing repeated multiplication of the same segment.

Does this problem relate to a common interview pattern?

Yes, it combines array manipulation with math, specifically prefix products, to optimize range-based calculations in streams.

#1352

Medium

auto_awesome数组·数学

LeetCode 题解工作台

最后 K 个数的乘积

设计一个算法，该算法接受一个整数流并检索该流中最后 k 个整数的乘积。实现 ProductOfNumbers 类： ProductOfNumbers() 用一个空的流初始化对象。 void add(int num) 将数字 num 添加到当前数字列表的最后面。 int getProduct(int…

数组数学设计数据流前缀和

题目描述

设计一个算法，该算法接受一个整数流并检索该流中最后 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⁴
add 和 getProduct 最多被调用 4 * 10⁴ 次。
在任何时间点流的乘积都在 32 位整数范围内。

进阶：您能否同时将 GetProduct 和 Add 的实现改为 O(1) 时间复杂度，而不是 O(k) 时间复杂度？

lightbulb

解题思路

方法一：前缀积

我们初始化一个数组 $s$ ，其中 $s[i]$ 表示前 $i$ 个数字的乘积。

当调用 add(num) 时，我们判断 num 是否为 $0$ ，若是，则将 $s$ 置为 [1]，否则将 $s$ 的最后一个元素乘以 num，并将结果添加到 $s$ 的末尾。

当调用 getProduct(k) 时，此时判断 $s$ 的长度是否小于等于 $k$ ，若是，则返回 $0$ ，否则返回 $s$ 的最后一个元素除以 $s$ 的倒数第 $k + 1$ 个元素。即 $s[-1] / s[-k - 1]$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为调用 add 的次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class ProductOfNumbers:
    def __init__(self):
        self.s = [1]

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

    def getProduct(self, k: int) -> int:
        return 0 if len(self.s) <= k else self.s[-1] // self.s[-k - 1]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Watch for zeros in the stream that reset cumulative products.
question_mark
Ensure getProduct runs in constant time without looping over last k elements.
question_mark
Expect discussion of edge cases with k larger than the current stream size.

warning

常见陷阱

外企场景

error
Dividing by zero without checking if the segment contains a zero.
error
Not updating prefix products correctly after adding a zero.
error
Mismanaging indices when the stream is shorter than k.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute sum instead of product for the last k numbers while still supporting zeros.
arrow_right_alt
Support dynamic removal of numbers from the end and adjust prefix products accordingly.
arrow_right_alt
Track the maximum product of any contiguous k-length subarray in a real-time stream.

help

常见问题

外企场景

继续练习

#1442 形成两个异或相等数组的三元组数目 #1248 统计「优美子数组」#1472 设计浏览器历史记录