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

约 5 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 LeetCode 75
标签
数组 排序 双指针 二分查找

题目描述

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

image-20260928234504422

image-20260928234504425

题意分析

对每个咒语，统计能与它组成成功数对的药水瓶数，成功条件是两者强度乘积大于等于 success。返回数组与咒语原来的顺序一一对应。

每个咒语独立统计全部药水，不会消耗药水；强度相同的多瓶药水仍分别计数。两类强度都是正数，乘积恰好等于阈值也算成功。

解法：药水排序后对每个咒语二分阈值

核心思路

[!blue]

如果为每个咒语遍历全部药水，需要重复做许多比较。先把药水按强度升序排序，固定一个正咒语后，乘积也随药水下标非递减，因此失败药水在左、成功药水在右，成功位置形成连续后缀。

只需二分找到第一个成功位置。用左闭右开区间 [lo, hi) 保存还未确定的部分：lo 左侧已经确认失败，hi 及其右侧已经确认成功。初始 hi = m，允许整个数组都失败时，边界最终停在数组末尾。

中点乘积达标时，它及右侧都成功，将 hi = mid，继续寻找更早的成功位置；不达标时，中点及左侧都失败，令 lo = mid + 1。两界相遇后，就是成功后缀的开头，瓶数为 m - lo；全成功得到 m，全失败得到零。

乘积最高可达到 $10^{10}$，必须先将操作数扩展为 64 位再相乘，不能在较窄类型溢出后才转换。只排序药水，不改变咒语顺序，逐个写入对应答案即可。

解题步骤

  1. 将药水强度升序排序，创建与咒语等长的答案数组。
  2. 对每个原顺序咒语，初始化二分边界 lo = 0、hi = m。
  3. 用宽整数比较当前咒语与中点药水的乘积是否达到阈值。
  4. 达标令 hi = mid，否则令 lo = mid + 1，直到两界相遇。
  5. 将 m - lo 写入当前咒语的答案，最后返回整组计数。

代码实现

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        // 排序让「是否成功」沿下标单调，二分才有立足点。
        Arrays.sort(potions);
        int m = potions.length;
        int[] ans = new int[spells.length];

        for (int i = 0; i < spells.length; i++) {
            // 左闭右开 [lo, hi)，hi = m 给「一瓶都配不上」留合法落点。
            int lo = 0;
            int hi = m;

            while (lo < hi) {
                int mid = (lo + hi) >>> 1;

                // 乘积可达 1e10，必须先转 long 再乘。若改用除法阈值，必须向上取整。
                if ((long) potions[mid] * spells[i] >= success) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }

            // lo 是第一个成功的下标，它右边（含自身）全部成功。
            ans[i] = m - lo;
        }

        return ans;
    }
}

import (
    "sort"
)

func successfulPairs(spells []int, potions []int, success int64) []int {
    // 排序让「是否成功」沿下标单调，二分才有立足点。
    sort.Ints(potions)
    m := len(potions)
    ans := make([]int, len(spells))
    for i, v := range spells {
        // 左闭右开 [lo, hi)，hi = m 给「一瓶都配不上」留合法落点。
        lo, hi := 0, m
        for lo < hi {
            mid := (lo + hi) / 2
            // 乘积可达 1e10，必须先转 int64 再乘。若改用除法阈值，必须向上取整。
            if int64(potions[mid])*int64(v) >= success {
                hi = mid
            } else {
                lo = mid + 1
            }
        }
        // lo 是第一个成功的下标，它右边（含自身）全部成功。
        ans[i] = m - lo
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(m\log(m+1)+n\log(m+1))$，m 为药水数、n 为咒语数；先排序一次，再为每个咒语执行边界二分。
  • 空间复杂度：输出为 $O(n)$，每次二分只用 $O(1)$ 状态；还包括所用库排序的实现相关辅助空间。当前排序会改变 potions 的原顺序。

关键点总结

[!green]

  • 正数乘法与排序共同提供失败前缀、成功后缀的单调结构。
  • 二分寻找首次成功的位置，数量由后缀长度直接得到。
  • 右边界可以等于数组长度，统一表达没有成功药水的情况。
  • 乘法前扩展类型，咒语保持原顺序，重复药水按瓶数保留。

易错点总结

[!yellow]

  • 使用 32 位先乘再转宽类型，溢出的结果无法通过事后转换恢复。
  • 把成功条件写成严格大于，漏掉乘积恰好达到阈值的组合。
  • 找到任意成功中点就返回，尚未确定其左侧还有多少成功药水。
  • 用整除 success / spell 当药水下界却没有向上取整，可能把不达标药水计入。
  • 排序咒语后没有记录原位置，答案顺序与题目输入不对应。
  • 对相同强度药水去重，题目统计瓶数而不是不同强度种数。

相似题目

题目 难度 关联与区别
35. 搜索插入位置 简单 同样寻找第一个满足条件的位置，允许返回数组末尾作为全部不满足的落点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/11531571
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！