题目大意：
最后 K 个数的乘积
请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
add(int num)
- 将数字
num添加到当前数字列表的最后面。
getProduct(int k)
- 返回当前数字列表中，最后
k个数字的乘积。 - 你可以假设当前列表中始终 至少 包含
k个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
示例：
解释： 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
提示：
add和getProduct两种操作加起来总共不会超过40000次。0 <= num <= 1001 <= k <= 40000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1352
解题思路分析：
看到求连续区间乘积的题，我们应该想到使用前缀数组来解题。数组中下标为i的值代表从开始到第i位所有数的乘积，如果求最后k个数的乘积时，答案应该等于所有数乘积除以最后k个数以外数字的乘积。这与之前讲过的前缀和数组的解题思路非常相似。比如：
[1,2,3,4]
它的前缀乘积数组应该是：
int[] pre =[1,2,6,24]
如果我们求最后2位的乘积应该是pre[3] / pre[1] = 24 / 2 = 12
但是，乘法必须考虑到数字0的情况，如果前面某一位上的数字是0，那么他之后的乘积都是0，这样我们计算后k个数的乘积时就无法得到争取的结果，比如：
[2,4,0,6,8]
它的前缀乘积数组应该是：
[2,8,0,0,0]
这时我们如果求最后两位的乘积，显然是无法通过前缀数组求解的。因此使用前缀数组解决乘积问题时，我们需要做出一些变化，当出现数字0时，我们清空数组，数组中只保存最后不为0部分的乘积，凡是k大于前缀数组长度时我们可以返回0，反之可以按照上面的方式求解。
实现代码：
// 定义前缀乘积数组
// 由于数组长度未知，本体使用List类来代替
List<Integer> list = new ArrayList<>();
public ProductOfNumbers() {
}
public void add(int num) {
// 如果当前数字为0，清空list
if(num==0){
list.clear();
return;
}
// 如果list中元素个数大于0，
if(list.size()>0){
// 当前的前缀乘积为前一个前缀乘积乘以当前数字
list.add(list.get(list.size()-1)*num);
}else{ // 如果list为空
// 将当前数字加入list
list.add(num);
}
}
public int getProduct(int k) {
// 如果k大于list中元素个数大小，说明最后k个长度的元素中包含0，
// 返回0
if(k>list.size()) return 0;
// 如果k等于list元素个数，那么返回list中最后一个元素
if(k==list.size()) return list.get(list.size()-1);
// 反之返回list中最后一个值除以最后k个值以外数字的乘积的商
return list.get(list.size()-1) / list.get(list.size()-k-1);
}本题解法执行时间为13ms。
Runtime: 13 ms, faster than 98.99% of Java online submissions for Product of the Last K Numbers.
Memory Usage: 54.4 MB, less than 100.00% of Java online submissions for Product of the Last K Numbers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1352-product-of-the-last-k-numbers-解题思路分析/