leetcode
leetcode 1251 ~ 1300
最后 K 个数的乘积

最后 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`查询?
在`ProductOfNumbers`的实现中,每当`add`方法接收到0作为输入时,前缀乘积数组会被重置为只包含一个元素1。这是因为0的存在使得之后所有的乘积结果都将为0,直到再次添加非零元素。因此,无论添加多少个连续的0,前缀数组都将维持在这个重置状态。在此状态下执行`getProduct`查询,如果`k`不为0,则查询结果将是0,因为它试图获取包含0的段的乘积。
🦆
为什么在`add`方法中遇到0要重置整个前缀乘积数组而不是简单地添加一个0?
在`add`方法中遇到0后不简单地添加一个0到前缀乘积数组,而是重置数组,是因为添加0将使得该点之后所有计算的乘积结果均为0,失去了维持前缀乘积的意义。通过重置数组并开始一个新的乘积序列,可以避免在执行`getProduct`查询时不必要的误导和性能损耗。这种处理方式简化了逻辑,保证了乘积的正确计算。
🦆
在`getProduct`方法中,如果`k`的值正好等于前缀乘积数组的长度,为什么结果不是前缀数组最后一个元素而是0?
当`k`的值等于前缀乘积数组的长度时,表示需要获取的乘积涵盖了整个数组的范围,其中包括初始化时的那个1。在这种情况下,如果数组长度等于`k`,则意味着在这个范围内存在至少一个0(因为只有遇到0才会重置数组),导致所有产品均为0。因此,按照实现逻辑,如果`k`等于或超过数组长度,将直接返回0。
🦆
前缀乘积数组的初始化为什么选择从1开始,而不是从0或其他数字开始?
前缀乘积数组从1开始初始化,是因为1是乘法的单位元素,即任何数字乘以1都不改变其值。这样做可以简化乘积的计算过程,使得在添加第一个元素时可以直接乘以1,得到该元素本身。如果从0开始,那么任何后续乘积都会变为0,而从其他数字开始则会错误地改变乘积的值。因此,从1开始是保证乘积正确性和计算简便性的最佳选择。

相关问题