題目資訊

題目編號: 1352
題目連結: Product of the Last K Numbers
主題: Array, Math, Design, Data Stream, Prefix Sum

題目敘述

設計一個演算法來接收一個整數流，並檢索該流中最後 $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 \leq num \leq 100$
$1 \leq k \leq 4 \times 10^4$
最多有 $4 \times 10^4$ 次 add 和 getProduct 調用。
在任何時間點，該流的乘積將適合在一個 32位元 整數中。

進一步考慮: 你能夠實現 GetProduct 和 Add 都在 $O(1)$ 時間複雜度而不是 $O(k)$ 時間複雜度嗎？

直覺

此問題要求設計一個資料結構，以有效管理整數流並計算最後 $k$ 個整數的乘積。挑戰在於高效地更新並查詢最近 $k$ 個元素的乘積，特別是面對會打斷乘法連續性的零。我們的重點是維持計算這些乘積所需的資訊，而不必在每次查詢時從頭重新計算。

解法

我們採用類似動態規劃的方法，用一個名為 prefixProduct 的向量儲存該流中數字的累積乘積。具體來說，prefixProduct[i] 儲存的是前 $i$ 個數的乘積，而 prefixProduct[0] 初始化為 1 以簡化計算。

初始化：
- 我們用一個元素 1 初始化 prefixProduct。這作為计算累積乘積的基本情況，使我們能一致地處理乘積計算。
新增數字 (add 方法)：
- 當新增一個數字 num 時，行為會根據 num 是否為零而分支。
- 若 num 是零： 零會打斷乘積序列的連續性。因此，整個 prefixProduct 除了最初始的 1 之外都會重置。這意味著包含這個零的任何乘積查詢結果應為零。
- 若 num 非零： 透過將 prefixProduct.back() * num 添加到 prefixProduct 來延續累積乘積，從而維護到當前數字的運行乘積。
檢索乘積 (getProduct 方法)：
- 要檢索最後 $k$ 個數的乘積，我們需要確定乘積序列是否包含重置點。
- 若 $k \geq \text{prefixProduct.size()}$： 這表示在過去的 $k$ 個元素中出現過零，因為在遇到零時 prefixProduct 的大小被重置。在這種情況下，乘積為零，因為在範圍內有零。
- 否則： 最後 $k$ 個數的乘積是我們當前點的所有數的累積乘積除以最後的 $k$ 個數之前的累積乘積。這可以表示為： $$ \text{product} = \frac{\text{prefixProduct.back()}}{\text{prefixProduct}[\text{prefixProduct.size()} - k - 1]} $$

透過此高效處理乘積序列並仔細管理零的發生，我們得以在 $O(1)$ 的時間複雜度下執行 add 和 getProduct 操作。此方法利用了累積乘積陣列中乘法和除法的特性，即使在流中動態更新時也能保持效率。

程式碼

C++

class ProductOfNumbers {
public:
    // 用來儲存數字的前綴積的向量
    vector<int> prefixProduct{1};

    // 建構子初始化物件並使其為空的流
    ProductOfNumbers() {}

    // 將數字加入流中
    void add(int num) {
        if (num == 0) {
            // 如果數字是零，重設前綴積的列表
            prefixProduct.clear();
            prefixProduct.emplace_back(1);
        } else {
            // 將列表中最後一個數字的積與當前數字相乘後加入
            prefixProduct.emplace_back(prefixProduct.back() * num);
        }
    }

    // 獲得流中最後k個數字的積
    int getProduct(int k) {
        // 如果k較前綴積的大小大，表示在最後k個數字中有零存在，所以積為0
        return (k >= prefixProduct.size()) ? 0 : prefixProduct.back() / prefixProduct[prefixProduct.size() - k - 1];
    }
};

/**
    * 您的 ProductOfNumbers 物件將被這樣實例化和使用：
    * ProductOfNumbers* obj = new ProductOfNumbers();
    * obj->add(num);
    * int param_2 = obj->getProduct(k);
    */

Python

class ProductOfNumbers:
    # 用來存儲數字的前綴積的列表
    prefixProduct = [1]

    # 構造函數初始化對象為空流
    def __init__(self):
        pass

    # 將一個數字添加到流中
    def add(self, num: int):
        if num == 0:
            # 如果數字為零，重置前綴積列表
            self.prefixProduct.clear()
            self.prefixProduct.append(1)
        else:
            # 添加列表中最後一個數字與當前數字的乘積
            self.prefixProduct.append(self.prefixProduct[-1] * num)

    # 獲取流中最後 k 個數字的積
    def getProduct(self, k: int) -> int:
        # 如果 k 大於等於前綴積的大小，這意味著在最後的 k 個數字中有一個零，所以乘積是 0
        return 0 if k >= len(self.prefixProduct) else self.prefixProduct[-1] // self.prefixProduct[len(self.prefixProduct) - k - 1]


# 類的使用示例：
# productOfNumbers = ProductOfNumbers()
# productOfNumbers.add(3)
# productOfNumbers.add(0)
# productOfNumbers.add(2)
# productOfNumbers.add(5)
# productOfNumbers.add(4)
# print(productOfNumbers.getProduct(2)) # 輸出 20
# print(productOfNumbers.getProduct(3)) # 輸出 40
# print(productOfNumbers.getProduct(4)) # 輸出 0
# productOfNumbers.add(8)
# print(productOfNumbers.getProduct(2)) # 輸出 32

複雜度分析

時間複雜度: add(int num) 方法的時間複雜度為 $O(1)$，因為它涉及恆定數量的操作，無論輸入的大小或前綴乘積列表的大小如何變化。getProduct(int k) 方法也具有 $O(1)$ 的時間複雜度，因為它涉及恆定數量的算術操作和條件檢查。因此，這兩個方法都在恆定時間內運行。
空間複雜度: 空間複雜度為 $O(n)$，其中 $n$ 是對 add 方法的調用次數。這是因為 prefixProduct 向量隨著添加的元素數量線性增長，因為它對於每一次 add 調用存儲一個額外的元素。

CS Note
En

Leetcode 1352. Product of the Last K Numbers

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析