1352. Product of the Last K Numbers

 一刷 07/2022

Version #1 Prefix Product

一个需要学的的地方就是对0的处理

当一段subarray elements包含0的时候这一段的product也是0

所以我们只需要记录0之后的prefix product

如果last k element 超出了有记录的长度，就证明是0

Time O(1) to add, O(1) to get product

Space O(N)

Runtime: 21 ms, faster than 72.32% of Java online submissions for Product of the Last K Numbers.

Memory Usage: 75.8 MB, less than 64.79% of Java online submissions for Product of the Last K Numbers.

class ProductOfNumbers {

    private List<Integer> prefixProduct;

    public ProductOfNumbers() {

        prefixProduct = new ArrayList<>();

        prefixProduct.add(1);

    }

    

    public void add(int num) {

        if (num == 0) {

            prefixProduct = new ArrayList<>();

            prefixProduct.add(1);

        } else {

            int prev = prefixProduct.get(prefixProduct.size() - 1);

            prefixProduct.add(prev * num);

        }

    }

    

    public int getProduct(int k) {

        // last index is prefixProduct.size() - 1

        // first index is prefixProduct.size() - 1 - k

        int lastIndex = prefixProduct.size() - 1;

        return lastIndex - k >= 0 ? prefixProduct.get(lastIndex) / prefixProduct.get(lastIndex - k) : 0;

    }

}