MediumRating 1474

1352. Product of the Last K Numbers

arraymathdesigndata-streamprefix-sum

解題說明

Product of the Last K Numbers

題目描述：設計一個類別 ProductOfNumbers，支援兩個操作：add(num) 將數字加入串流，getProduct(k) 回傳最近 k 個數字的乘積。

解題思路：使用前綴乘積（prefix product）的概念。維護一個前綴乘積陣列 prefix，其中 prefix[i] 表示從某個起點到第 i 個數字的累積乘積。當加入非零數字時，prefix 尾端乘以新數字。查詢最近 k 個數字的乘積即為 prefix.back() / prefix[prefix.size()-1-k]。遇到 0 時，之前所有的前綴乘積都失效，需要重新開始。

C++ 解法

複雜度分析

時間複雜度：add 和 getProduct 均為 O(1)

空間複雜度：O(n) — 其中 n 為自上次出現 0 以來加入的數字數量

虛擬碼

1. Initialize prefix = [1]
2. add(num):
   a. If num == 0: reset prefix to [1] (products including 0 are always 0)
   b. Else: append prefix.back() * num to prefix
3. getProduct(k):
   a. If k >= prefix.size(): return 0 (range includes a zero)
   b. Return prefix.back() / prefix[prefix.size() - 1 - k]

其他解法

方法二：暴力法 儲存所有數字，getProduct 時遍歷最近 k 個數字相乘。add 為 O(1)，getProduct 為 O(k)。簡單但查詢效率低。

方法三：段落式前綴乘積 遇到 0 時不清空，而是記錄 0 的位置。查詢時先檢查範圍內是否有 0。空間利用率較好，但實現較複雜。

延伸思考

如果數字可能非常大，乘積溢出怎麼辦？你會如何處理？（提示：考慮用對數）
如果需要支援 getSum(k) 回傳最近 k 個數字的和，你會如何修改設計？
在多執行緒環境下，如何確保 add 和 getProduct 的執行緒安全？

Product of the Last K Numbers — CaffeCode