原文链接: https://leetcode-cn.com/problems/product-of-the-last-k-numbers

英文原文

Design an algorithm that accepts a stream of integers and retrieves the product of the last k integers of the stream.

Implement the ProductOfNumbers class:

• ProductOfNumbers() Initializes the object with an empty stream.
• void add(int num) Appends the integer num to the stream.
• int getProduct(int k) Returns the product of the last k numbers in the current list. You can assume that always the current list has at least k numbers.

The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

 

Example:

Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output
[null,null,null,null,null,null,20,40,0,null,32]

Explanation
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); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32 

 

Constraints:

• 0 <= num <= 100
• 1 <= k <= 4 * 104
• At most 4 * 104 calls will be made to add and getProduct.
• The product of the stream at any point in time will fit in a 32-bit integer.

中文题目

请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：

1. add(int num)

• 将数字 num 添加到当前数字列表的最后面。

2. getProduct(int k)

• 返回当前数字列表中，最后 k 个数字的乘积。
• 你可以假设当前列表中始终 至少 包含 k 个数字。

题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。

 

示例：

输入：
["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 

 

提示：

• add 和 getProduct 两种操作加起来总共不会超过 40000 次。
• 0 <= num <= 100
• 1 <= k <= 40000

通过代码

高赞题解

思路

这道题比较直观就是要维护前缀积列表products，如果没有0的话，那很简单，直接products.get(products.size() - 1) / products.get(products.size() - 1- k)就可以了，那么该如何处理0的情况？

我们知道只要某个数为0，那么它前面的那些数就都没有用了，我们直接清理掉就好了。题目中说了K是小于数据长度的，如果维护的前缀积列表长度小于K，那么说明在后K个中出现过的0，因此长度不够K，这种情况下直接返回0就行；否则按照上面的逻辑就可以了，由于要维护乘积，所以列表的第一个元素添加一个1作为辅助元素。

总结

其实这个题很简单，只要好好想想怎么处理0就行了。

时间复杂度

O(1)

代码

class ProductOfNumbers {


  private List<Integer> products;

  public ProductOfNumbers() {
    products = new ArrayList<>();
    products.add(1);
  }

  public void add(int num) {
    if(num == 0){
      products = new ArrayList<>();
      products.add(1);
    } else {
      products.add(products.get(products.size() - 1) * num);
    }
  }

  public int getProduct(int k) {
    if(products.size() <= k ){
      return 0;
    }
    return products.get(products.size() - 1) / products.get(products.size() - 1- k);
  }
}

进阶

看评论区有小伙伴问如果是求任意区间怎么办？这个是很好的进阶问题，讲下思路:

需要改的地方有两处：

1. 增加一个维护所有0位置的列表
2. 遇到0时前面的数据不清除，直接在后面接着放就行了，出现0的位置放一个1以便后面使用。也就是上面题解中add()函数里的第二行去掉，对于上面题解不去掉是一种优化。

那么在add()时加入以上逻辑，时间复杂度O(1)，getProduct()方法就用二分搜索0是否出现在查询的区间中，其他相同，时间复杂度O(lgn)

进一步优化

上面是通过记录所有0的位置然后二分去判断是否有0，经过评论区的小伙伴提醒：还可以通过记录一个0的前缀和数组来实现O(1)时间复杂度来判断区间中是否包含0。

代码

应下面小伙伴的需求，贴一下进阶问题的代码

class ProductOfNumbers {

  private List<Integer> list;
  private List<Integer> cnt0; //前缀和记录0的个数

  public ProductOfNumbers() {
    list = new ArrayList<>();
    cnt0 = new ArrayList<>();
    list.add(1);
    cnt0.add(0);
  }

  public void add(int num) {
    if (num == 0) {
      list.add(1);
      cnt0.add(cnt0.get(cnt0.size() - 1) + 1);
    } else {
      list.add(list.get(list.size() - 1) * num);
      cnt0.add(cnt0.get(cnt0.size() - 1));
    }
  }

  public int getProduct(int k) {
    return getProduct(list.size() - k, list.size() - 1);
  }

  // 表示的是第s个元素到第e个元素间的乘积
  public int getProduct(int s, int e) {
    if (e < 1 || e >= list.size() || s < 1 || s >= list.size() || s > e) {
      throw new RuntimeException("Invalid input");
    }
    if (!cnt0.get(s - 1).equals(cnt0.get(e))) {
      return 0;
    }
    return list.get(e) / list.get(s - 1);
  }
}

统计信息

通过次数	提交次数	AC比率
7019	15680	44.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言