今日题目

https://leetcode.com/problems/product-of-the-last-k-numbers/description/

思路

  • 情况一：流中没有 0： 此时直接用前缀乘积即可满足题目要求。
  • 情况二：流中存在 0： 那结果必然是 0！

因此，我们只需判断最后 k 个数中是否包含 0。若包含，直接返回 0。

解法

  1. 用数组维护乘法前缀积。
  2. 检查最后 k 个数中是否出现过 0。

复杂度

  • 时间复杂度：$O(Q)$，Q 为操作次数。

  • 空间复杂度：$O(Q)$，Q 为操作次数。

代码

class ProductOfNumbers:

    def __init__(self):
        self.q = []
        self.mul = 1

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

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


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

image.png