最后 K 个数的乘积
难度:
标签:
题目描述
代码结果
运行时间: 126 ms, 内存: 29.5 MB
/* 思路: 使用Java Stream API进行流式处理。我们将通过将所有数字存储在列表中并按需计算乘积。Java的Stream API提供了一种方便的方式来处理集合数据。 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
public class ProductOfNumbers {
private List<Integer> nums;
public ProductOfNumbers() {
nums = new ArrayList<>();
}
public void add(int num) {
if (num == 0) {
nums.clear();
}
nums.add(num);
}
public int getProduct(int k) {
if (nums.size() < k) return 0;
return IntStream.range(nums.size() - k, nums.size())
.map(nums::get)
.reduce(1, (a, b) -> a * b);
}
}
解释
方法:
这个题解使用了前缀乘积数组来快速计算指定范围内数字的乘积。通过维护一个数组,每个元素存储从列表开始到当前位置的所有数字的乘积。当添加一个新数字时,若数字为0,则重置数组因为任何数乘以0都是0,这相当于重新开始一段新的序列;若非0,则将其乘以前缀数组的最后一个元素(即当前所有元素的乘积)并追加到数组末尾。对于查询操作,利用前缀乘积,通过最后一个元素除以第len(prefix)-k-1个元素的结果来获得最后k个元素的乘积。若k等于或大于数组长度,意味着中间出现了0,因此返回0。
时间复杂度:
O(1)
空间复杂度:
O(n)
代码细节讲解
🦆
在实现`ProductOfNumbers`类时,如何处理连续多个0的情况,特别是在多次`add(0)`操作后的`getProduct`查询?
▷🦆
为什么在`add`方法中遇到0要重置整个前缀乘积数组而不是简单地添加一个0?
▷🦆
在`getProduct`方法中,如果`k`的值正好等于前缀乘积数组的长度,为什么结果不是前缀数组最后一个元素而是0?
▷🦆
前缀乘积数组的初始化为什么选择从1开始,而不是从0或其他数字开始?
▷