LEETCODE 1352. Product of the Last K Numbers 解题思路分析

题目大意：

最后 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 <= 100
• 1 <= 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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1352-product-of-the-last-k-numbers-解题思路分析/