@ninijia 在 Leetcode每日一题练习 ------ 1352. 最后 K 个数的乘积 中发帖
从Leetcode 每日一题练习继续讨论:
1352. 最后 K 个数的乘积
1352. Product of the Last K Numbers
题解
本题注意要求添加和获取尾部乘积的时间复杂度都为O(1),添加数字比较简单,直接向数组尾部添加数字就能满足时间复杂度,计算乘积相对来说复杂一些,因为添加数字是从前向后添加,此处考虑如果是获取尾部的k个数字的和,首先想到的就是使用前缀和,用n对应的前缀和和n-k对应的前缀和做差即得尾部的k个数字的和,前缀和的好处在于从前向后添加数字的过程中可以一边添加数字一边计算出来且计算出来后不会发生变化,后续不需要额外的计算,但后缀和在向尾部添加数字的时前面数字的后缀和一直在改变。
本题也可以采用类似的思路,只是使用的不是前缀和而是前缀积,要获取尾部k个数字的积只需将n对应的前缀积和n-k对应的前缀积做除法。但乘积有一个特殊的因素,即出现0的情...