2300. 咒语和药水的成功对数

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。同时给你一个整数 success 。一个咒语和药水的能量强度相乘如果大于等于success ，那么它们视为一对成功的组合。请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的药水数目。

示例 1：

输入： spells = 5,1,3, potions = 1,2,3,4,5, success = 7 输出：4,0,3解释：
第 0 个咒语：5 *1,2,3,4,5 = 5,10,15,20,25 。总共 4 个成功组合。
第 1 个咒语：1 * 1,2,3,4,5 = 1,2,3,4,5 。总共 0 个成功组合。
第 2 个咒语：3 *1,2,3,4,5 = 3,6,9,12,15 。总共 3 个成功组合。所以返回 4,0,3 。

示例 2：

输入： spells = 3,1,2, potions = 8,5,8, success = 16 输出：2,0,2解释：
第 0 个咒语：3 *8,5,8 = 24,15,24 。总共 2 个成功组合。
第 1 个咒语：1 * 8,5,8 = 8,5,8 。总共 0 个成功组合。
第 2 个咒语：2 *8,5,8 = 16,10,16 。总共 2 个成功组合。所以返回 2,0,2 。

提示：

n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def successfulPairs(self, spells, potions, success):
        mx = max(potions)
        cnt = [0] * (mx + 1)
        for y in potions:
            cnt[y] += 1
        
        for i in range(mx - 1, -1, -1):  # 后缀和 → cnt[i] 代表强度 >= i 的药水总数量
            cnt[i] += cnt[i + 1]
        
        for i, x in enumerate(spells):
            low = (success - 1) // x + 1  # 计算当前咒语 x 至少需要多大的药水 low 才能满足 x*y >= success
            spells[i] = cnt[low] if low <= mx else 0
        return spells
        """
        :type spells: List[int]
        :type potions: List[int]
        :type success: int
        :rtype: List[int]
        """