给你一个由 n 个整数组成的数组 nums 和一个整数 k，请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：

• 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
• 这两个子数组必须是 相邻的，即 b = a + k。

如果可以找到这样的 两个 子数组，请返回 true；否则返回 false。

子数组 是数组中的一个连续 非空 的元素序列。

示例 1：

示例 2：

提示：

• 2 <= nums.length <= 100
• 1 <= 2 * k <= nums.length
• -1000 <= nums[i] <= 1000

Problem: 3349. 检测相邻递增子数组 I

[TOC]

思路

根据滑动窗口的最小值的解题方法，我们可以用同样的方法来解决本题，前几天的每日一题也是可以用相同的办法这么做长度为 K 的子数组的能量值 II

做题方法：

• 维护两个相邻的滑动窗口，每一个窗口功能都一样：用于维护长度为k的子数组中的最小值(这里不懂可以做一下滑动窗口最大值，可以说是最经典的滑窗题了)
• 如果滑动窗口的长度为k，那么就说明该子数组是一直递增的，那么如果有两个相邻的滑动窗口的大小都为k，则说明两段都是递增的,return true;即可

复杂度

• 时间复杂度: $O(N)$
• 空间复杂度: $O(N)$

Code

###C++

class Solution {
public:
    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        deque<int> q1,q2;
        for(int i=0,j=k;j<nums.size();j++,i++){
            if(q1.size()&&q1.front()<i-k+1)
                q1.pop_front();
            if(q2.size()&&q2.front()<j-k+1)
                q2.pop_front();
            while(q1.size()&&nums[q1.back()]>=nums[i])
                q1.pop_back();
            while(q2.size()&&nums[q2.back()]>=nums[j])
                q2.pop_back();
            q1.push_back(i);
            q2.push_back(j);
            if(q1.size()==k&&q2.size()==k)
                return true;
        }
        return false;
    }
};


//可以这样，使用滑动窗口来做这个题，维护两个滑窗，然后判断每次
//滑动的时候判断当前窗口的大小是否等于k，如果两个窗口都等于
//k，那么说明可以构成连续的两个相邻严格递增子数组了

解法一

思路和算法

两个相邻的长度为 $k$ 的子数组等价于一个长度为 $2k$ 的子数组。遍历数组 $\textit{nums}$ 中的每个长度为 $2k$ 的子数组，判断该子数组是否满足前 $k$ 个元素与后 $k$ 个元素分别严格递增。如果找到符合要求的子数组，则返回 $\text{true}$；如果未找到符合要求的子数组，则返回 $\text{false}$。

代码

###Java

class Solution {
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int n = nums.size();
        for (int i = 0; i + 2 * k <= n; i++) {
            if (isIncreasingSubarray(nums, i, i + k - 1) && isIncreasingSubarray(nums, i + k, i + 2 * k - 1)) {
                return true;
            }
        }
        return false;
    }

    public boolean isIncreasingSubarray(List<Integer> nums, int start, int end) {
        for (int i = start; i < end; i++) {
            if (nums.get(i) >= nums.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
}

###C#

public class Solution {
    public bool HasIncreasingSubarrays(IList<int> nums, int k) {
        int n = nums.Count;
        for (int i = 0; i + 2 * k <= n; i++) {
            if (IsIncreasingSubarray(nums, i, i + k - 1) && IsIncreasingSubarray(nums, i + k, i + 2 * k - 1)) {
                return true;
            }
        }
        return false;
    }

    public bool IsIncreasingSubarray(IList<int> nums, int start, int end) {
        for (int i = start; i < end; i++) {
            if (nums[i] >= nums[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(nk)$，其中 $n$ 是数组 $\textit{nums}$ 的长度，$k$ 是给定的整数。需要遍历的长度为 $2k$ 的子数组的数量是 $O(n)$，每个子数组的遍历时间是 $O(k)$。

• 空间复杂度：$O(1)$。

解法二

思路和算法

数组 $\textit{nums}$ 的长度是 $n$。将数组 $\textit{nums}$ 拆分成一个或多个最长严格递增子数组，满足每个最长严格递增子数组都非空且任意两个相邻最长严格递增子数组合并之后的新子数组不是严格递增子数组。当数组 $\textit{nums}$ 中存在两个相邻的长度为 $k$ 的严格递增子数组时，有如下两种情况。

• 两个长度为 $k$ 的严格递增子数组合并之后仍是严格递增子数组，则数组 $\textit{nums}$ 中存在长度至少为 $2k$ 的严格递增子数组。

• 两个长度为 $k$ 的严格递增子数组合并之后不是严格递增子数组，则数组 $\textit{nums}$ 中存在两个相邻最长严格递增子数组的长度分别至少为 $k$。

为了判断是否存在两个相邻的长度为 $k$ 的严格递增子数组，需要计算每个最长严格递增子数组的长度，分别考虑两种情况。

用 $\textit{maxIncreasing}$ 表示两个相邻严格递增子数组的最大长度，初始时 $\textit{maxIncreasing} = 0$。从左到右遍历数组 $\textit{nums}$，遍历过程中维护上一个最长严格递增子数组的长度 $\textit{prevIncreasing}$ 与当前最长严格递增子数组的长度 $\textit{currIncreasing}$，初始时 $\textit{prevIncreasing} = \textit{currIncreasing} = 0$。对于遍历到的每个下标 $i$，执行如下操作。

1. 将 $\textit{currIncreasing}$ 的值增加 $1$。

2. 当 $i = n - 1$ 或 $\textit{nums}[i] \ge \textit{nums}[i + 1]$ 时，下标 $i$ 是一个最长严格递增子数组的结束下标，因此需要更新答案并更新 $\textit{maxIncreasing}$、$\textit{prevIncreasing}$ 与 $\textit{currIncreasing}$。

   1. 如果两个相邻严格递增子数组合并之后仍是严格递增子数组，则两个相邻严格递增子数组的最大长度分别是 $\Big\lfloor \dfrac{\textit{currIncreasing}}{2} \Big\rfloor$，使用 $\Big\lfloor \dfrac{\textit{currIncreasing}}{2} \Big\rfloor$ 更新 $\textit{maxIncreasing}$。

   2. 如果两个相邻严格递增子数组合并之后不是严格递增子数组，则两个相邻严格递增子数组的最大长度分别是 $\min(\textit{prevIncreasing}, \textit{currIncreasing})$，使用 $\min(\textit{prevIncreasing}, \textit{currIncreasing})$ 更新 $\textit{maxIncreasing}$。

   3. 由于一个最长严格递增子数组遍历结束，因此将 $\textit{prevIncreasing}$ 的值更新为 $\textit{currIncreasing}$，将 $\textit{currIncreasing}$ 的值更新为 $0$。

遍历结束之后，如果 $\textit{maxIncreasing} \ge k$ 则返回 $\text{true}$，如果 $\textit{maxIncreasing} < k$ 则返回 $\text{false}$。

代码

###Java

class Solution {
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int maxIncreasing = 0;
        int n = nums.size();
        int prevIncreasing = 0, currIncreasing = 0;
        for (int i = 0; i < n && maxIncreasing < k; i++) {
            currIncreasing++;
            if (i == n - 1 || nums.get(i) >= nums.get(i + 1)) {
                maxIncreasing = Math.max(maxIncreasing, currIncreasing / 2);
                maxIncreasing = Math.max(maxIncreasing, Math.min(prevIncreasing, currIncreasing));
                prevIncreasing = currIncreasing;
                currIncreasing = 0;
            }
        }
        return maxIncreasing >= k;
    }
}

###C#

public class Solution {
    public bool HasIncreasingSubarrays(IList<int> nums, int k) {
        int maxIncreasing = 0;
        int n = nums.Count;
        int prevIncreasing = 0, currIncreasing = 0;
        for (int i = 0; i < n && maxIncreasing < k; i++) {
            currIncreasing++;
            if (i == n - 1 || nums[i] >= nums[i + 1]) {
                maxIncreasing = Math.Max(maxIncreasing, currIncreasing / 2);
                maxIncreasing = Math.Max(maxIncreasing, Math.Min(prevIncreasing, currIncreasing));
                prevIncreasing = currIncreasing;
                currIncreasing = 0;
            }
        }
        return maxIncreasing >= k;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历数组一次。

• 空间复杂度：$O(1)$。

思路和周赛第二题是一样的，判断答案是否 $\ge k$，请看 我的题解。

在神秘的地牢中，n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。

你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔法师为止。

换句话说，你将选择一个起点，然后以 k 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。

给定一个数组 energy 和一个整数k，返回你能获得的 最大 能量。

示例 1：

示例 2：

提示：

• 1 <= energy.length <= 105
• -1000 <= energy[i] <= 1000
• 1 <= k <= energy.length - 1

Problem: 100274. 从魔法师身上吸取的最大能量

[TOC]

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

###Python3

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        n = len(energy)
        mx = -inf
        for i in range(n - k,n):
            s = 0
            for j in range(i,-1,-k):
                s += energy[j]
                mx = max(mx,s)
        return mx

k = 1

从特殊到一般，先想一想，$k=1$ 怎么做？

此时只能一步一步地向右走。无论起点在哪，终点都是 $n-1$。

如果选择 $i$ 为起点，我们计算的是子数组 $[i,n-1]$ 的元素和，即后缀和。

后缀和怎么算？我们可以倒着遍历 $\textit{energy}$，同时累加元素和，即为后缀和。

答案等于所有后缀和的最大值。

k = 2

再想一想，$k=2$ 怎么做？

此时我们有两个终点：$n-2$ 和 $n-1$。

对于终点 $n-1$：

• 如果选择 $n-3$ 为起点，那么我们累加的是下标为 $n-3,n-1$ 的元素和。
• 如果选择 $n-5$ 为起点，那么我们累加的是下标为 $n-5,n-3,n-1$ 的元素和。
• 如果选择 $n-7$ 为起点，那么我们累加的是下标为 $n-7,n-5,n-3,n-1$ 的元素和。
• 一般地，从 $n-1$ 开始倒着遍历，步长为 $-k=-2$，累加元素和，计算元素和的最大值。

对于终点 $n-2$：

• 如果选择 $n-4$ 为起点，那么我们累加的是下标为 $n-4,n-2$ 的元素和。
• 如果选择 $n-6$ 为起点，那么我们累加的是下标为 $n-6,n-4,n-2$ 的元素和。
• 如果选择 $n-8$ 为起点，那么我们累加的是下标为 $n-8,n-6,n-4,n-2$ 的元素和。
• 一般地，从 $n-2$ 开始倒着遍历，步长为 $-k=-2$，累加元素和，计算元素和的最大值。

是否可以从 $n-3$ 开始倒着遍历？

不行，因为 $n-3$ 还可以向右跳到 $n-1$，所以 $n-3$ 不是终点，不能作为倒着遍历的起点。

一般情况

枚举终点 $n-k,n-k+1,\dots,n-1$，倒着遍历，步长为 $-k$。

遍历的同时累加元素和 $\textit{sufSum}$，计算 $\textit{sufSum}$ 的最大值，即为答案。

写法一

###py

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        n = len(energy)
        ans = -inf
        for i in range(n - k, n):  # 枚举终点 i
            suf_sum = accumulate(energy[j] for j in range(i, -1, -k))  # 计算后缀和
            ans = max(ans, max(suf_sum))
        return ans

###java

class Solution {
    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length;
        int ans = Integer.MIN_VALUE;
        for (int i = n - k; i < n; i++) { // 枚举终点 i
            int sufSum = 0;
            for (int j = i; j >= 0; j -= k) {
                sufSum += energy[j]; // 计算后缀和
                ans = Math.max(ans, sufSum);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        int ans = INT_MIN;
        for (int i = n - k; i < n; i++) { // 枚举终点 i
            int suf_sum = 0;
            for (int j = i; j >= 0; j -= k) {
                suf_sum += energy[j]; // 计算后缀和
                ans = max(ans, suf_sum);
            }
        }
        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int maximumEnergy(int* energy, int energySize, int k){
    int ans = INT_MIN;
    for (int i = energySize - k; i < energySize; i++) { // 枚举终点 i
        int suf_sum = 0;
        for (int j = i; j >= 0; j -= k) {
            suf_sum += energy[j]; // 计算后缀和
            ans = MAX(ans, suf_sum);
        }
    }
    return ans;
}

###go

func maximumEnergy(energy []int, k int) int {
n := len(energy)
ans := math.MinInt
for i := n - k; i < n; i++ { // 枚举终点 i
sufSum := 0
for j := i; j >= 0; j -= k {
sufSum += energy[j] // 计算后缀和
ans = max(ans, sufSum)
}
}
return ans
}

###js

var maximumEnergy = function(energy, k) {
    const n = energy.length;
    let ans = -Infinity;
    for (let i = n - k; i < n; i++) { // 枚举终点 i
        let sufSum = 0;
        for (let j = i; j >= 0; j -= k) {
            sufSum += energy[j]; // 计算后缀和
            ans = Math.max(ans, sufSum);
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn maximum_energy(energy: Vec<i32>, k: i32) -> i32 {
        let n = energy.len();
        let k = k as usize;
        let mut ans = i32::MIN;
        for i in n - k..n { // 枚举终点 i
            let mut suf_sum = 0;
            for j in (0..=i).rev().step_by(k) {
                suf_sum += energy[j]; // 计算后缀和
                ans = ans.max(suf_sum);
            }
        }
        ans
    }
}

写法二

原地计算后缀和，把后缀和保存到 $\textit{energy}$ 中。

最后返回 $\textit{energy}$ 的最大值，即为所有后缀和的最大值。

###py

class Solution:
    def maximumEnergy(self, energy: List[int], k: int) -> int:
        for i in range(len(energy) - k - 1, -1, -1):
            energy[i] += energy[i + k]
        return max(energy)

###java

class Solution {
    public int maximumEnergy(int[] energy, int k) {
        for (int i = energy.length - k - 1; i >= 0; i--) {
            energy[i] += energy[i + k];
        }
        return Arrays.stream(energy).max().getAsInt();
    }
}

###cpp

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size();
        for (int i = n - k - 1; i >= 0; i--) {
            energy[i] += energy[i + k];
        }
        return ranges::max(energy);
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int maximumEnergy(int* energy, int energySize, int k) {
    int ans = INT_MIN;
    for (int i = energySize - 1; i >= 0; i--) {
        if (i + k < energySize) {
            energy[i] += energy[i + k];
        }
        ans = MAX(ans, energy[i]);
    }
    return ans;
}

###go

func maximumEnergy(energy []int, k int) int {
for i := len(energy) - k - 1; i >= 0; i-- {
energy[i] += energy[i+k]
}
return slices.Max(energy)
}

###js

var maximumEnergy = function(energy, k) {
    for (let i = energy.length - k - 1; i >= 0; i--) {
        energy[i] += energy[i + k];
    }
    return Math.max(...energy);
};

###rust

impl Solution {
    pub fn maximum_energy(mut energy: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        for i in (0..energy.len() - k).rev() {
            energy[i] += energy[i + k];
        }
        *energy.iter().max().unwrap()
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{energy}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面贪心与思维题单的「§5.3 逆向思维」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：递推

我们定义 $f[i]$ 表示巫师 $i$ 完成上一瓶药水的时间。

对于当前的药水 $x$，我们需要计算每个巫师完成该药水的时间。定义 $\textit{tot}$ 表示当前药水完成的时间，初始时 $\textit{tot} = 0$。

对于每个巫师 $i$，他开始处理当前药水的时间为 $\max(\textit{tot}, f[i])$，处理该药水需要的时间为 $skill[i] \times mana[x]$，因此他完成该药水的时间为 $\max(\textit{tot}, f[i]) + skill[i] \times mana[x]$。我们更新 $\textit{tot}$ 为该值。

由于酿造过程要求药水在当前巫师完成工作后必须立即传递给下一个巫师并开始处理，因此我们需要更新每个巫师完成上一瓶药水的时间 $f[i]$。对于最后一个巫师 $n-1$，我们直接将 $f[n-1]$ 更新为 $\textit{tot}$。对于其他巫师 $i$，我们可以通过倒序遍历来更新 $f[i]$，具体地，$f[i] = f[i+1] - skill[i+1] \times mana[x]$。

最终 $f[n-1]$ 即为所有药水酿造完成的最短总时间。

###python

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        max = lambda a, b: a if a > b else b
        n = len(skill)
        f = [0] * n
        for x in mana:
            tot = 0
            for i in range(n):
                tot = max(tot, f[i]) + skill[i] * x
            f[-1] = tot
            for i in range(n - 2, -1, -1):
                f[i] = f[i + 1] - skill[i + 1] * x
        return f[-1]

###java

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        long[] f = new long[n];
        for (int x : mana) {
            long tot = 0;
            for (int i = 0; i < n; ++i) {
                tot = Math.max(tot, f[i]) + skill[i] * x;
            }
            f[n - 1] = tot;
            for (int i = n - 2; i >= 0; --i) {
                f[i] = f[i + 1] - skill[i + 1] * x;
            }
        }
        return f[n - 1];
    }
}

###cpp

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size();
        vector<long long> f(n);
        for (int x : mana) {
            long long tot = 0;
            for (int i = 0; i < n; ++i) {
                tot = max(tot, f[i]) + 1LL * skill[i] * x;
            }
            f[n - 1] = tot;
            for (int i = n - 2; i >= 0; --i) {
                f[i] = f[i + 1] - 1LL * skill[i + 1] * x;
            }
        }
        return f[n - 1];
    }
};

###go

func minTime(skill []int, mana []int) int64 {
n := len(skill)
f := make([]int64, n)
for _, x := range mana {
var tot int64
for i := 0; i < n; i++ {
tot = max(tot, f[i]) + int64(skill[i])*int64(x)
}
f[n-1] = tot
for i := n - 2; i >= 0; i-- {
f[i] = f[i+1] - int64(skill[i+1])*int64(x)
}
}
return f[n-1]
}

###ts

function minTime(skill: number[], mana: number[]): number {
    const n = skill.length;
    const f: number[] = Array(n).fill(0);
    for (const x of mana) {
        let tot = 0;
        for (let i = 0; i < n; ++i) {
            tot = Math.max(tot, f[i]) + skill[i] * x;
        }
        f[n - 1] = tot;
        for (let i = n - 2; i >= 0; --i) {
            f[i] = f[i + 1] - skill[i + 1] * x;
        }
    }
    return f[n - 1];
}

时间复杂度 $O(n \times m)$，空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别为巫师和药水的数量。

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~

给你两个长度分别为 n 和 m 的整数数组 skill 和 mana 。

在一个实验室里，有 n 个巫师，他们必须按顺序酿造 m 个药水。每个药水的法力值为 mana[j]，并且每个药水 必须 依次通过 所有 巫师处理，才能完成酿造。第 i 个巫师在第 j 个药水上处理需要的时间为 timeij = skill[i] * mana[j]。

由于酿造过程非常精细，药水在当前巫师完成工作后 必须 立即传递给下一个巫师并开始处理。这意味着时间必须保持 同步，确保每个巫师在药水到达时 马上 开始工作。

返回酿造所有药水所需的 最短 总时间。

示例 1：

示例 2：

示例 3：

提示：

• n == skill.length
• m == mana.length
• 1 <= n, m <= 5000
• 1 <= mana[i], skill[i] <= 5000

解法：DP

设 $f(i, j)$ 表示巫师 $j$ 完成药水 $i$ 的时间，且暂时不考虑这瓶药水后面的步骤。这个时间受到三个限制：

1. 巫师 $(j - 1)$ 需要先完成这个药水，巫师 $j$ 才能开始酿造，即 $f(i, j) \xleftarrow{\max} f(i, j - 1) + s_jm_i$。
2. 巫师 $j$ 需要先完成上一瓶药水才能开始酿造，即 $f(i, j) \xleftarrow{\max} f(i - 1, j) + s_jm_i$。
3. 巫师 $j$ 完成这瓶药水时，巫师 $(j + 1)$ 也要完成上一瓶药水，即 $f(i, j) \xleftarrow{\max} f(i - 1, j + 1)$。

这样我们就能算出巫师 $n$ 完成药水 $i$ 的时间。注意，由于 $f(i, j)$ 没有考虑这瓶药水后面的步骤，所以可能会出现 $f(i, j) + s_{j + 1}m_i < f(i, j + 1)$ 的情况。因此我们还要从 $f(i, n)$ 开始倒推，计算 $f(i, j) = f(i, j + 1) - s_{j + 1}m_i$，把每名巫师真实的完成时间算出来。

复杂度 $\mathcal{O}(nm)$。

参考代码（c++）

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();

        // 空间优化：去掉了 DP 的第一维
        long long f[n + 2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; i++) {
            // 正推计算巫师 j 完成药水 i，且不考虑后面步骤的时间
            for (int j = 1; j <= n; j++) f[j] = max(max(f[j - 1], f[j]) + skill[j - 1] * mana[i - 1], f[j + 1]);
            // 倒推计算巫师 j 完成药水 i 的真实时间
            for (int j = n - 1; j > 0; j--) f[j] = f[j + 1] - skill[j] * mana[i - 1];
        }

        return f[n];
    }
};

方法一：正反两次扫描

为了计算酿造药水的时间，定义 $\textit{lastFinish}[i]$ 表示巫师 $i$ 完成上一瓶药水的时间。

示例 1 在处理完 $\textit{mana}[0]$ 后，有

$$
\textit{lastFinish} = [5,30,40,60]
$$

如果接着 $\textit{lastFinish}$ 继续酿造下一瓶药水 $\textit{mana}[1]=1$，完成时间是多少？注意开始酿造的时间不能早于 $\textit{lastFinish}[i]$。

题目要求「药水在当前巫师完成工作后必须立即传递给下一个巫师并开始处理」，也就是说，酿造药水的过程中是不能有停顿的。

从 $64$ 开始倒推，可以得到每名巫师的实际完成时间。比如倒数第二位巫师的完成时间，就是 $64$ 减去最后一名巫师花费的时间 $4\cdot 1$，得到 $60$。

按照上述过程处理每瓶药水，最终答案为 $\textit{lastFinish}[n-1]$。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        last_finish = [0] * n  # 第 i 名巫师完成上一瓶药水的时间
        for m in mana:
            # 按题意模拟
            sum_t = 0
            for x, last in zip(skill, last_finish):
                if last > sum_t: sum_t = last  # 手写 max
                sum_t += x * m
            # 倒推：如果酿造药水的过程中没有停顿，那么 last_finish[i] 应该是多少
            last_finish[-1] = sum_t
            for i in range(n - 2, -1, -1):
                last_finish[i] = last_finish[i + 1] - skill[i + 1] * m
        return last_finish[-1]

###java

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        long[] lastFinish = new long[n]; // 第 i 名巫师完成上一瓶药水的时间
        for (int m : mana) {
            // 按题意模拟
            long sumT = 0;
            for (int i = 0; i < n; i++) {
                sumT = Math.max(sumT, lastFinish[i]) + skill[i] * m;
            }
            // 倒推：如果酿造药水的过程中没有停顿，那么 lastFinish[i] 应该是多少
            lastFinish[n - 1] = sumT;
            for (int i = n - 2; i >= 0; i--) {
                lastFinish[i] = lastFinish[i + 1] - skill[i + 1] * m;
            }
        }
        return lastFinish[n - 1];
    }
}

###cpp

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size();
        vector<long long> last_finish(n); // 第 i 名巫师完成上一瓶药水的时间
        for (int m : mana) {
            // 按题意模拟
            long long sum_t = 0;
            for (int i = 0; i < n; i++) {
                sum_t = max(sum_t, last_finish[i]) + skill[i] * m;
            }
            // 倒推：如果酿造药水的过程中没有停顿，那么 lastFinish[i] 应该是多少
            last_finish[n - 1] = sum_t;
            for (int i = n - 2; i >= 0; i--) {
                last_finish[i] = last_finish[i + 1] - skill[i + 1] * m;
            }
        }
        return last_finish[n - 1];
    }
};

###go

func minTime(skill, mana []int) int64 {
n := len(skill)
lastFinish := make([]int, n) // 第 i 名巫师完成上一瓶药水的时间
for _, m := range mana {
// 按题意模拟
sumT := 0
for i, x := range skill {
sumT = max(sumT, lastFinish[i]) + x*m
}
// 倒推：如果酿造药水的过程中没有停顿，那么 lastFinish[i] 应该是多少
lastFinish[n-1] = sumT
for i := n - 2; i >= 0; i-- {
lastFinish[i] = lastFinish[i+1] - skill[i+1]*m
}
}
return int64(lastFinish[n-1])
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{skill}$ 的长度，$m$ 是 $\textit{mana}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：递推开始时间

由于酿造药水的过程是连续的，所以知道了开始时间（或者完成时间）就能知道每个 $\textit{lastFinish}[i]$。所以 $\textit{lastFinish}$ 数组是多余的。

设开始酿造 $\textit{mana}[j]$ 的时间为 $\textit{start}_j$，那么有

$$
\textit{lastFinish}_j[i] = \textit{start}j + \textit{mana}[j]\cdot \sum{k=0}^{i} \textit{skill}[k]
$$

在已知 $\textit{start}_{j-1}$ 的前提下，能否递推算出 $\textit{start}_j$？

哪位巫师决定了开始时间？假设第 $i$ 位巫师决定了开始时间，那么这位巫师完成 $\textit{mana}[j-1]$ 的时间，同时也是他开始 $\textit{mana}[j]$ 的时间。

所以有

$$
\textit{lastFinish}_{j-1}[i] + \textit{mana}[j]\cdot \textit{skill}[i] = \textit{lastFinish}_j[i]
$$

两边代入 $\textit{lastFinish}_j[i]$ 的式子，得

$$
\textit{start}{j-1} + \textit{mana}[j-1]\cdot \sum{k=0}^{i} \textit{skill}[k] + \textit{mana}[j]\cdot \textit{skill}[i] = \textit{start}j + \textit{mana}[j]\cdot \sum{k=0}^{i} \textit{skill}[k]
$$

移项得

$$
\textit{start}j = \textit{start}{j-1} + \textit{mana}[j-1]\cdot \sum_{k=0}^{i} \textit{skill}[k] - \textit{mana}[j]\cdot \sum_{k=0}^{i-1} \textit{skill}[k]
$$

计算 $\textit{skill}$ 的 前缀和 数组 $s$，上式为

$$
\textit{start}j = \textit{start}{j-1} + \textit{mana}[j-1]\cdot s[i+1] - \textit{mana}[j]\cdot s[i]
$$

枚举 $i$，取最大值，得

$$
\textit{start}j = \textit{start}{j-1} + \max_{i=0}^{n-1} \left{\textit{mana}[j-1]\cdot s[i+1] - \textit{mana}[j]\cdot s[i]\right}
$$

初始值 $\textit{start}_0 = 0$。

答案为 $\textit{lastFinish}{m-1}[n-1] = \textit{start}{m-1} + \textit{mana}[m-1]\cdot s[n]$。

###py

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        s = list(accumulate(skill, initial=0))  # skill 的前缀和
        start = 0
        for pre, cur in pairwise(mana):
            start += max(pre * s[i + 1] - cur * s[i] for i in range(n))
        return start + mana[-1] * s[-1]

###java

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        int[] s = new int[n + 1]; // skill 的前缀和
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + skill[i];
        }

        int m = mana.length;
        long start = 0;
        for (int j = 1; j < m; j++) {
            long mx = 0;
            for (int i = 0; i < n; i++) {
                mx = Math.max(mx, (long) mana[j - 1] * s[i + 1] - (long) mana[j] * s[i]);
            }
            start += mx;
        }
        return start + (long) mana[m - 1] * s[n];
    }
}

###cpp

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();
        vector<int> s(n + 1); // skill 的前缀和
        partial_sum(skill.begin(), skill.end(), s.begin() + 1);

        long long start = 0;
        for (int j = 1; j < m; j++) {
            long long mx = 0;
            for (int i = 0; i < n; i++) {
                mx = max(mx, 1LL * mana[j - 1] * s[i + 1] - 1LL * mana[j] * s[i]);
            }
            start += mx;
        }
        return start + 1LL * mana[m - 1] * s[n];
    }
};

###go

func minTime(skill, mana []int) int64 {
n, m := len(skill), len(mana)
s := make([]int, n+1) // skill 的前缀和
for i, x := range skill {
s[i+1] = s[i] + x
}

start := 0
for j := 1; j < m; j++ {
mx := 0
for i := range n {
mx = max(mx, mana[j-1]*s[i+1]-mana[j]*s[i])
}
start += mx
}
return int64(start + mana[m-1]*s[n])
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{skill}$ 的长度，$m$ 是 $\textit{mana}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。如果在遍历的同时计算前缀和，则可以做到 $\mathcal{O}(1)$ 空间。

方法三：record 优化

将递推式

$$
\textit{start}j = \textit{start}{j-1} + \max_{i=0}^{n-1} \left{\textit{mana}[j-1]\cdot s[i+1] - \textit{mana}[j]\cdot s[i]\right}
$$

变形为

$$
\textit{start}j = \textit{start}{j-1} + \max_{i=0}^{n-1} \left{(\textit{mana}[j-1]-\textit{mana}[j])\cdot s[i] + \textit{mana}[j-1]\cdot \textit{skill}[i] \right}
$$

设 $d = \textit{mana}[j-1]-\textit{mana}[j]$。分类讨论：

• 如果 $d > 0$。由于 $s$ 是单调递增数组，如果 $\textit{skill}[3] < \textit{skill}[5]$，那么 $i=3$ 绝对不会算出最大值；但如果 $\textit{skill}[3] > \textit{skill}[5]$，谁会算出最大值就不一定了。所以我们只需要考虑 $\textit{skill}$ 的逆序 record，这才是可能成为最大值的数据。其中逆序 record 的意思是，倒序遍历 $\textit{skill}$，每次遍历到更大的数，就记录下标。
• 如果 $d < 0$。由于 $s$ 是单调递增数组，如果 $\textit{skill}[5] < \textit{skill}[3]$，那么 $i=5$ 绝对不会算出最大值；但如果 $\textit{skill}[5] > \textit{skill}[3]$，谁会算出最大值就不一定了。所以我们只需要考虑 $\textit{skill}$ 的正序 record，这才是可能成为最大值的数据。其中正序 record 的意思是，正序遍历 $\textit{skill}$，每次遍历到更大的数，就记录下标。
• $d = 0$ 的情况可以并入 $d>0$ 的情况。

###py

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        s = list(accumulate(skill, initial=0))

        suf_record = [n - 1]
        for i in range(n - 2, -1, -1):
            if skill[i] > skill[suf_record[-1]]:
                suf_record.append(i)

        pre_record = [0]
        for i in range(1, n):
            if skill[i] > skill[pre_record[-1]]:
                pre_record.append(i)

        start = 0
        for pre, cur in pairwise(mana):
            record = pre_record if pre < cur else suf_record
            start += max(pre * s[i + 1] - cur * s[i] for i in record)
        return start + mana[-1] * s[-1]

###java

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + skill[i];
        }

        List<Integer> suf = new ArrayList<>();
        suf.add(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            if (skill[i] > skill[suf.getLast()]) {
                suf.add(i);
            }
        }

        List<Integer> pre = new ArrayList<>();
        pre.add(0);
        for (int i = 1; i < n; i++) {
            if (skill[i] > skill[pre.getLast()]) {
                pre.add(i);
            }
        }

        int m = mana.length;
        long start = 0;
        for (int j = 1; j < m; j++) {
            List<Integer> record = mana[j - 1] < mana[j] ? pre : suf;
            long mx = 0;
            for (int i : record) {
                mx = Math.max(mx, (long) mana[j - 1] * s[i + 1] - (long) mana[j] * s[i]);
            }
            start += mx;
        }
        return start + (long) mana[m - 1] * s[n];
    }
}

###java

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + skill[i];
        }

        int[] suf = new int[n];
        int sufLen = 0;
        suf[sufLen++] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (skill[i] > skill[suf[sufLen - 1]]) {
                suf[sufLen++] = i;
            }
        }

        int[] pre = new int[n];
        int preLen = 0;
        pre[preLen++] = 0;
        for (int i = 1; i < n; i++) {
            if (skill[i] > skill[pre[preLen - 1]]) {
                pre[preLen++] = i;
            }
        }

        int m = mana.length;
        long start = 0;
        for (int j = 1; j < m; j++) {
            int[] record = mana[j - 1] < mana[j] ? pre : suf;
            int recordLen = mana[j - 1] < mana[j] ? preLen : sufLen;
            long mx = 0;
            for (int k = 0; k < recordLen; k++) {
                int i = record[k];
                mx = Math.max(mx, (long) mana[j - 1] * s[i + 1] - (long) mana[j] * s[i]);
            }
            start += mx;
        }
        return start + (long) mana[m - 1] * s[n];
    }
}

###cpp

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();
        vector<int> s(n + 1);
        partial_sum(skill.begin(), skill.end(), s.begin() + 1);

        vector<int> suf = {n - 1};
        for (int i = n - 2; i >= 0; i--) {
            if (skill[i] > skill[suf.back()]) {
                suf.push_back(i);
            }
        }

        vector<int> pre = {0};
        for (int i = 1; i < n; i++) {
            if (skill[i] > skill[pre.back()]) {
                pre.push_back(i);
            }
        }

        long long start = 0;
        for (int j = 1; j < m; j++) {
            auto& record = mana[j - 1] < mana[j] ? pre : suf;
            long long mx = 0;
            for (int i : record) {
                mx = max(mx, 1LL * mana[j - 1] * s[i + 1] - 1LL * mana[j] * s[i]);
            }
            start += mx;
        }
        return start + 1LL * mana[m - 1] * s[n];
    }
};

###go

func minTime(skill, mana []int) int64 {
n, m := len(skill), len(mana)
s := make([]int, n+1)
for i, x := range skill {
s[i+1] = s[i] + x
}

suf := []int{n - 1}
for i := n - 2; i >= 0; i-- {
if skill[i] > skill[suf[len(suf)-1]] {
suf = append(suf, i)
}
}

pre := []int{0}
for i := 1; i < n; i++ {
if skill[i] > skill[pre[len(pre)-1]] {
pre = append(pre, i)
}
}

start := 0
for j := 1; j < m; j++ {
record := suf
if mana[j-1] < mana[j] {
record = pre
}
mx := 0
for _, i := range record {
mx = max(mx, mana[j-1]*s[i+1]-mana[j]*s[i])
}
start += mx
}
return int64(start + mana[m-1]*s[n])
}

复杂度分析（最坏情况）

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{skill}$ 的长度，$m$ 是 $\textit{mana}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

复杂度分析（平均情况）

力扣喜欢出随机数据，上述算法在随机数据下的性能如何？

换句话说，在随机数据下，record 的期望长度是多少？

为方便分析，假设 $\textit{skill}$ 是一个随机的 $[1,n]$ 的排列。

$\textit{skill}[i]$ 如果是一个新的最大值，那么它是 $[0,i]$ 中的最大值。在随机排列的情况下，$[0,i]$ 中的排列也是随机的，所以这等价于该排列的最后一个数是最大值的概率，即

$$
\dfrac{1}{i+1}
$$

record 的期望长度，等于「每个位置能否成为新的最大值」之和，能就贡献 $1$，不能就贡献 $0$。

所以 $\textit{skill}[i]$ 给期望的贡献是 $\dfrac{1}{i+1}$。所以 record 的期望长度为

$$
\sum_{i=0}^{n-1} \dfrac{1}{i+1}
$$

由调和级数可知，record 的期望长度为 $\Theta(\log n)$。

• 时间复杂度：$\Theta(n + m\log n)$，其中 $n$ 是 $\textit{skill}$ 的长度，$m$ 是 $\textit{mana}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法四：凸包 + 二分

前置知识：二维计算几何，凸包，Andrew 算法。

把递推式

$$
\textit{start}j = \textit{start}{j-1} + \max_{i=0}^{n-1} \left{(\textit{mana}[j-1]-\textit{mana}[j])\cdot s[i] + \textit{mana}[j-1]\cdot \textit{skill}[i] \right}
$$

中的

$$
(\textit{mana}[j-1]-\textit{mana}[j])\cdot s[i] + \textit{mana}[j-1]\cdot \textit{skill}[i]
$$

改成点积的形式，这样我们能得到来自几何意义上的观察。

设向量 $\mathbf{v}_i = (s[i],\textit{skill}[i])$。

设向量 $\mathbf{p} = (\textit{mana}[j-1]-\textit{mana}[j], \textit{mana}[j-1])$。

那么我们求的是

$$
\max_{i=0}^{n-1} \mathbf{p}\cdot \mathbf{v}_i
$$

根据点积的几何意义，我们求的是 $\mathbf{v}_i$ 在 $\mathbf{p}$ 方向上的投影长度，再乘以 $\mathbf{p}$ 的模长 $||\mathbf{p}||$。由于 $||\mathbf{p}||$ 是个定值，所以要最大化投影长度。

考虑 $\mathbf{v}_i$ 的上凸包（用 Andrew 算法计算），在凸包内的点，就像是山坳，比凸包顶点的投影长度短。所以只需考虑凸包顶点。

这样有一个很好的性质：顺时针（或者逆时针）遍历凸包顶点，$\mathbf{p}\cdot \mathbf{v}_i$ 会先变大再变小（单峰函数）。那么要计算最大值，就类似 852. 山脉数组的峰顶索引，二分首个「下坡」的位置，具体见 我的题解。

###py

class Vec:
    __slots__ = 'x', 'y'

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __sub__(self, b: "Vec") -> "Vec":
        return Vec(self.x - b.x, self.y - b.y)

    def det(self, b: "Vec") -> int:
        return self.x * b.y - self.y * b.x

    def dot(self, b: "Vec") -> int:
        return self.x * b.x + self.y * b.y

class Solution:
    # Andrew 算法，计算 points 的上凸包
    # 由于横坐标（前缀和）是严格递增的，所以无需排序
    def convex_hull(self, points: List[Vec]) -> List[Vec]:
        q = []
        for p in points:
            while len(q) > 1 and (q[-1] - q[-2]).det(p - q[-1]) >= 0:
                q.pop()
            q.append(p)
        return q

    def minTime(self, skill: List[int], mana: List[int]) -> int:
        s = list(accumulate(skill, initial=0))
        vs = [Vec(pre_sum, x) for pre_sum, x in zip(s, skill)]
        vs = self.convex_hull(vs)  # 去掉无用数据

        start = 0
        for pre, cur in pairwise(mana):
            p = Vec(pre - cur, pre)
            # p.dot(vs[i]) 是个单峰函数，二分找最大值
            check = lambda i: p.dot(vs[i]) > p.dot(vs[i + 1])
            i = bisect_left(range(len(vs) - 1), True, key=check)
            start += p.dot(vs[i])
        return start + mana[-1] * s[-1]

###java

class Solution {
    private record Vec(int x, int y) {
        Vec sub(Vec b) {
            return new Vec(x - b.x, y - b.y);
        }

        long det(Vec b) {
            return (long) x * b.y - (long) y * b.x;
        }

        long dot(Vec b) {
            return (long) x * b.x + (long) y * b.y;
        }
    }

    // Andrew 算法，计算 points 的上凸包
    // 由于横坐标（前缀和）是严格递增的，所以无需排序
    private List<Vec> convexHull(Vec[] points) {
        List<Vec> q = new ArrayList<>();
        for (Vec p : points) {
            while (q.size() > 1 && q.getLast().sub(q.get(q.size() - 2)).det(p.sub(q.getLast())) >= 0) {
                q.removeLast();
            }
            q.add(p);
        }
        return q;
    }

    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        int[] s = new int[n + 1];
        Vec[] points = new Vec[n];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + skill[i];
            points[i] = new Vec(s[i], skill[i]);
        }
        List<Vec> vs = convexHull(points); // 去掉无用数据

        int m = mana.length;
        long start = 0;
        for (int j = 1; j < m; j++) {
            Vec p = new Vec(mana[j - 1] - mana[j], mana[j - 1]);
            // p.dot(vs[i]) 是个单峰函数，二分找最大值
            int l = -1, r = vs.size() - 1;
            while (l + 1 < r) {
                int mid = (l + r) >>> 1;
                if (p.dot(vs.get(mid)) > p.dot(vs.get(mid + 1))) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            start += p.dot(vs.get(r));
        }
        return start + (long) mana[m - 1] * s[n];
    }
}

###cpp

struct Vec {
    int x, y;
    Vec operator-(const Vec& b) { return {x - b.x, y - b.y}; }
    long long det(const Vec& b) { return 1LL * x * b.y - 1LL * y * b.x; }
    long long dot(const Vec& b) { return 1LL * x * b.x + 1LL * y * b.y; }
};

class Solution {
    // Andrew 算法，计算 points 的上凸包
    // 由于横坐标（前缀和）是严格递增的，所以无需排序
    vector<Vec> convex_hull(vector<Vec>& points) {
        vector<Vec> q;
        for (auto& p : points) {
            while (q.size() > 1 && (q.back() - q[q.size() - 2]).det(p - q.back()) >= 0) {
                q.pop_back();
            }
            q.push_back(p);
        }
        return q;
    }

public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();
        vector<int> s(n + 1);
        vector<Vec> vs(n);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + skill[i];
            vs[i] = {s[i], skill[i]};
        }
        vs = convex_hull(vs); // 去掉无用数据

        long long start = 0;
        for (int j = 1; j < m; j++) {
            Vec p = {mana[j - 1] - mana[j], mana[j - 1]};
            // p.dot(vs[i]) 是个单峰函数，二分找最大值
            int l = -1, r = vs.size() - 1;
            while (l + 1 < r) {
                int mid = l + (r - l) / 2;
                (p.dot(vs[mid]) > p.dot(vs[mid + 1]) ? r : l) = mid;
            }
            start += p.dot(vs[r]);
        }
        return start + 1LL * mana[m - 1] * s[n];
    }
};

###go

type vec struct{ x, y int }

func (a vec) sub(b vec) vec { return vec{a.x - b.x, a.y - b.y} }
func (a vec) det(b vec) int { return a.x*b.y - a.y*b.x }
func (a vec) dot(b vec) int { return a.x*b.x + a.y*b.y }

// Andrew 算法，计算 points 的上凸包
// 由于横坐标（前缀和）是严格递增的，所以无需排序
func convexHull(points []vec) (q []vec) {
for _, p := range points {
for len(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).det(p.sub(q[len(q)-1])) >= 0 {
q = q[:len(q)-1]
}
q = append(q, p)
}
return
}

func minTime(skill, mana []int) int64 {
n, m := len(skill), len(mana)
s := make([]int, n+1)
vs := make([]vec, n)
for i, x := range skill {
s[i+1] = s[i] + x
vs[i] = vec{s[i], x}
}
vs = convexHull(vs) // 去掉无用数据

start := 0
for j := 1; j < m; j++ {
p := vec{mana[j-1] - mana[j], mana[j-1]}
// p.dot(vs[i]) 是个单峰函数，二分找最大值
i := sort.Search(len(vs)-1, func(i int) bool { return p.dot(vs[i]) > p.dot(vs[i+1]) })
start += p.dot(vs[i])
}
return int64(start + mana[m-1]*s[n])
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n + m\log n)$，其中 $n$ 是 $\textit{skill}$ 的长度，$m$ 是 $\textit{mana}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

Code

###Python3

import numpy as np

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        dp = np.zeros(n + 1)
        C = np.array([0] + skill).cumsum()
        for x in mana:
            T = C * x
            F = np.max(dp[1:] - T[:-1])
            dp = T + F
        return int(dp[-1])

给你两个正整数数组 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

排序 + 二分

为了方便，我们将 spells 记为 a，将 potions 记为 b，将 success 记为 t。

对于每个 $a[i]$，有多少个 $b[j]$ 满足 $a[i] \times b[j] \geqslant t$，等价于问数组 b 中值大于等于 $\frac{t}{a[i]}$ 的个数，这容易让我们想到先对数组 b 排升序，再通过二分找到满足该条件的最小下标，从该下标到数组结尾，均为满足条件的 $b[j]$。

代码：

###Java

class Solution {
    public int[] successfulPairs(int[] a, int[] b, long t) {
        int n = a.length, m = b.length;
        int[] ans = new int[n];
        Arrays.sort(b);
        for (int i = 0; i < n; i++) {
            double cur = t * 1.0 / a[i];
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (b[mid] >= cur) r = mid;
                else l = mid + 1;
            }
            if (b[r] * 1L * a[i] >= t) ans[i] = m - r;
        }
        return ans;
    }
}

###Python

class Solution:
    def successfulPairs(self, a: List[int], b: List[int], t: int) -> List[int]:
        # n, m = len(a), len(b)
        # b.sort()
        # ans = [0] * n
        # for i in range(n):
        #     cur = t / a[i]
        #     l, r = 0, m - 1
        #     while l < r:
        #         mid = l + r >> 1
        #         if b[mid] >= cur: r = mid
        #         else: l = mid + 1
        #     ans[i] = m - r if b[r] * a[i] >= t else 0
        # return ans
        b.sort()
        return [len(b) - bisect_left(b, t / x) for x in a]

###C++

class Solution {
public:
    vector<int> successfulPairs(vector<int>& a, vector<int>& b, long long t) {
        // int n = a.size(), m = b.size();
        // vector<int> ans(n);
        // sort(b.begin(), b.end());
        // for (int i = 0; i < n; i++) {
        //     double cur = t * 1.0 / a[i];
        //     int l = 0, r = m - 1;
        //     while (l < r) {
        //         int mid = l + r >> 1;
        //         if (b[mid] >= cur) r = mid;
        //         else l = mid + 1;
        //     }
        //     if (b[r] * 1L * a[i] >= t) ans[i] = m - r;
        // }
        // return ans;
        int n = a.size(), m = b.size();
        vector<int> ans(n);
        sort(b.begin(), b.end());
        for (int i = 0; i < n; i++) ans[i] = b.end() - lower_bound(b.begin(), b.end(), t * 1.0 / a[i]);
        return ans;
    }
};

###TypeScript

function successfulPairs(a: number[], b: number[], t: number): number[] {
    const n = a.length, m = b.length;
    const ans = new Array(n).fill(0);
    b.sort((a,b)=>a-b);
    for (let i = 0; i < n; i++) {
        const cur = t * 1.0 / a[i];
        let l = 0, r = m - 1;
        while (l < r) {
            const mid = l + r >> 1;
            if (b[mid] >= cur) r = mid;
            else l = mid + 1;
        }
        if (b[r] * a[i] >= t) ans[i] = m - r;
    }
    return ans;
};

• 时间复杂度：对数组 b 排序的复杂度为 $O(m\log{m})$；构建答案时，每次在值域 $[0, m - 1]$ 范围内进行二分，复杂度为 $O(n\log{m})$。整体复杂度为 $O(m\log{m} + n\log{m})$
• 空间复杂度：$O(\log{m} + n)$

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

所有题解已经加入 刷题指南，欢迎 star 哦 ~

方法一：二分查找

思路与算法

对于某一个咒语的能量，我们可以采用二分查找的方法来高效地找到符合条件的药水数量。首先，我们将 $\textit{potions}$ 数组进行排序，以便能够利用有序性进行二分查找。然后，对于每个咒语 $\textit{spells}[i]$，$0 \le i < n$，其中 $n$ 为数组 $\textit{spells}$ 的长度，我们计算出目标值

$$target = \lceil \frac{\textit{success}}{\textit{spells}[i]} \rceil$$

其中 $\lceil x \rceil$ 表示不小于 $x$ 的最小整数。$\textit{target}$ 代表了在当前咒语强度下，药水需要达到的最低强度。接下来，我们使用「二分查找」来在数组 $\textit{potions}$ 中找到第一个大于等于 $target$ 的元素的索引 $\textit{idx}$，进一步可以得到此时表示成功组合的药水数量为 $m - \textit{idx}$，其中 $m$ 表示数组 $\textit{potions}$ 的长度。

代码

###C++

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> res;
        for (auto& i : spells) {
            long long t = (success + i - 1) / i - 1;
            res.push_back(potions.size() - (upper_bound(potions.begin(), potions.end(), t) - potions.begin()));
        }
        return res;
    }
};

###Java

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length, m = potions.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            long t = (success + spells[i] - 1) / spells[i] - 1;
            res[i] = m - binarySearch(potions, 0, m - 1, t);
        }
        return res;
    }

    public int binarySearch(int[] arr, int lo, int hi, long target) {
        int res = hi + 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] > target) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }
}

###C#

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        Array.Sort(potions);
        int n = spells.Length, m = potions.Length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            long t = (success + spells[i] - 1) / spells[i] - 1;
            res[i] = m - BinarySearch(potions, 0, m - 1, t);
        }
        return res;
    }

    public int BinarySearch(int[] arr, int lo, int hi, long target) {
        int res = hi + 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] > target) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }
}

###C

static int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int binarySearch(const int *arr, int lo, int hi, long long target) {
    int res = hi + 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > target) {
            res = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return res;
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    qsort(potions, potionsSize, sizeof(int), cmp);
    int *res = (int *)calloc(spellsSize, sizeof(int));
    for (int i = 0; i < spellsSize; i++) {
        long long t = (success - 1) / spells[i];
        res[i] = potionsSize - binarySearch(potions, 0, potionsSize - 1, t);
    }
    *returnSize = spellsSize;
    return res;
}

###Python

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        return [len(potions) - bisect.bisect_right(potions, (success - 1) // i) for i in spells]

###Go

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Ints(potions)
    res := make([]int, len(spells))
    for i, x := range spells {
        res[i] = len(potions) - sort.SearchInts(potions, (int(success) - 1) / x + 1)
    }
    return res
}

###JavaScript

var successfulPairs = function(spells, potions, success) {
    function binarySearch(nums, lo, hi, target) {
        let res = hi + 1;
        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (nums[mid] > target) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }

    potions.sort((a, b) => a - b);
    return spells.map((item) => {
        return potions.length - binarySearch(potions, 0, potions.length - 1, (success - 1) / item)
    })
};

复杂度分析

• 时间复杂度：$O(m \times \log m + n \times \log m)$，其中 $n$ 为数组 $\textit{spells}$ 的长度，$m$ 是数组 $\textit{postion}$ 的长度，主要为对数组 $\textit{potions}$ 排序和对数组 $\textit{spells}$ 中每一个元素对数组 $\textit{potions}$ 进行「二分查找」的时间开销。
• 空间复杂度：$O(\log m)$，主要为对 $\textit{potions}$ 排序的空间开销，其中返回的答案不计入空间复杂度。

方法二：双指针

思路与算法

同样我们也可以通过「双指针」来解决这个问题：

首先我们对数组 $\textit{spells}$ 下标按照其位置上的能量强度进行 升序排序，假设其排序后的数组为 $\textit{idx}$，对数组 $\textit{potions}$ 按照能量强度进行 降序排序。并初始化一个结果数组 $\textit{res}$，长度为 $n$，$n$ 为数组 $\textit{spells}$ 的长度，用于记录每个咒语成功组合的药水数目。

我们使用两个指针 $i$ 和 $j$ 分别指向数组 $\textit{idx}$ 和 $\textit{potions}$ 的起始位置，用指针 $i$ 遍历数组 $\textit{idx}$，对于当前 $i$ 指向的咒语 $\textit{spells}[\textit{idx}[i]]$，若有

$$
\textit{spells}[\textit{idx}[i]] \times \textit{potions}[j] \ge \textit{sucess} \tag{1}
$$

成立，则对于任意 $i < k < n$，都有

$$
\textit{spells}[\textit{idx}[k]] \times \textit{potions}[j] \ge \textit{sucess} \tag{2}
$$

成立。对于每一个 $i$，指针 $j$ 不断右移直至 $j$ 不满足条件 $(1)$（其中右移前需要满足 $j < m$ 成立，$m$ 为 $\textit{potions}$ 的长度）。对于指针 $i$，指针 $j$ 移动操作结束后，那么此时能成功组合的药水数量 $\textit{res}[\textit{idx}[i]] = j$。并且由于随着指针 $i$ 位置不断增大，指针 $j$ 的位置单调不减，所以指针 $i$ 不断右移的整个过程时间复杂度为 $O(n)$。

代码

###C++

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> res(spells.size());
        vector<int> idx(spells.size());
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return spells[a] < spells[b];
        });
        sort(potions.begin(), potions.end(), [](int a, int b) {
            return a > b;
        });
        for (int i = 0, j = 0; i < spells.size(); ++i) {
            int p = idx[i];
            int v = spells[p];
            while (j < potions.size() && (long long) potions[j] * v >= success) {
                ++j;
            }
            res[p] = j;
        }
        return res;
    }
};

###Java

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length, m = potions.length;
        int[] res = new int[n];
        int[][] idx = new int[n][2];
        for (int i = 0; i < n; ++i) {
            idx[i][0] = spells[i];
            idx[i][1] = i;
        }
        Arrays.sort(potions);
        for (int i = 0, j = m - 1; i < j; ++i, --j) {
            int temp = potions[i];
            potions[i] = potions[j];
            potions[j] = temp;
        }
        Arrays.sort(idx, (a, b) -> a[0] - b[0]);
        for (int i = 0, j = 0; i < n; ++i) {
            int p = idx[i][1];
            int v = idx[i][0];
            while (j < m && (long) potions[j] * v >= success) {
                ++j;
            }
            res[p] = j;
        }
        return res;
    }
}

###C#

public class Solution {
    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.Length, m = potions.Length;
        int[] res = new int[n];
        int[][] idx = new int[n][];
        for (int i = 0; i < n; ++i) {
            idx[i] = new int[2];
            idx[i][0] = spells[i];
            idx[i][1] = i;
        }
        Array.Sort(potions);
        for (int i = 0, j = m - 1; i < j; ++i, --j) {
            int temp = potions[i];
            potions[i] = potions[j];
            potions[j] = temp;
        }
        Array.Sort(idx, (a, b) => a[0] - b[0]);
        for (int i = 0, j = 0; i < n; ++i) {
            int p = idx[i][1];
            int v = idx[i][0];
            while (j < m && (long) potions[j] * v >= success) {
                ++j;
            }
            res[p] = j;
        }
        return res;
    }
}

###C

static int cmp1(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

static int cmp2(const void *a, const void *b) {
    return ((int *)a)[0] - ((int *)b)[0];
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    int *res = (int *)calloc(spellsSize, sizeof(int));
    int idx[spellsSize][2];
    for (int i = 0; i < spellsSize; i++) {
        idx[i][0] = spells[i];
        idx[i][1] = i;
    }

    qsort(potions, potionsSize, sizeof(int), cmp1);
    qsort(idx, spellsSize, sizeof(idx[0]), cmp2);
    for (int i = 0, j = 0; i < spellsSize; ++i) {
        int p = idx[i][1];
        int v = idx[i][0];
        while (j < potionsSize && (long long) potions[j] * v >= success) {
            ++j;
        }
        res[p] = j;
    }
    *returnSize = spellsSize;
    return res;
}

###Python

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        res = [0] * len(spells)
        idx = [i for i in range(len(spells))]
        idx.sort(key = lambda x: spells[x])
        potions.sort(key = lambda x : -x)
        j = 0
        for p in idx:
            v = spells[p]
            while j < len(potions) and potions[j] * v >= success:
                j += 1
            res[p] = j
        return res

###Go

func successfulPairs(spells []int, potions []int, success int64) []int {
    res := make([]int, len(spells))
    idx := make([]int, len(spells))
    for i, _ := range idx {
        idx[i] = i
    }
    sort.Slice(potions, func(i, j int) bool {
        return potions[i] > potions[j]
    })
    sort.Slice(idx, func(i, j int) bool {
        return spells[idx[i]] < spells[idx[j]]
    })
    j := 0
    for _, p := range idx {
        v := spells[p]
        for j < len(potions) && int64(potions[j]) * int64(v) >= success {
            j++
        }
        res[p] = j
    }
    return res
}

###JavaScript

var successfulPairs = function(spells, potions, success) {
    const res = new Array(spells.length).fill(0);
    const idx = new Array(spells.length).fill(0).map((_, i) => i);
    idx.sort((a, b) => spells[a] - spells[b]);
    potions.sort((a, b) => b - a);
    let j = 0;
    for (p of idx) {
        let v = spells[p];
        while (j < potions.length && potions[j] * v >= success) {
            j++;
        }
        res[p] = j;
    }
    return res;
};

复杂度分析

• 时间复杂度：$O(n \times \log n + m \times \log m)$，其中 $n$ 为数组 $\textit{spells}$ 的长度，$m$ 是数组 $\textit{postion}$ 的长度，主要为对数组 $\textit{potions}$ 和 $\textit{idx}$ 排序的时间开销。
• 空间复杂度：$O(n + \log n + \log m)$，主要为数组 $\textit{idx}$ 的空间开销和对数组 $\textit{potions}$ 排序的空间开销，其中返回的答案不计入空间复杂度。

方法一：排序 + 二分查找

写法一：使用浮点数

问题相当于给你 $n$ 个询问，每次问 $\textit{spells}[i]$ 与 $\textit{potions}$ 中的多少个数相乘，结果 $\ge \textit{success}$。

对 $\textit{potions}$ 排序后，就可以二分查找了：

• 设 $j$ 是最小的满足 $\textit{potions}[j]\ge\dfrac{\textit{success}}{\textit{spells}[i]}$ 的下标。
• 由于数组已经排序，那么下标大于 $j$ 的数也同样满足不等式。
• 从 $j$ 到 $m-1$，一共有 $m-j$ 个满足不等式的数，其中 $m$ 是 $\textit{potions}$ 的长度。

有关二分查找的原理，请看【基础算法精讲 04】。

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        return [m - bisect_left(potions, success / x) for x in spells]

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        for (int i = 0; i < spells.length; i++) {
            spells[i] = potions.length - lowerBound(potions, (double) success / spells[i]);
        }
        return spells;
    }

    // 返回 nums 中的第一个大于等于 target 的元素下标
    private int lowerBound(int[] nums, double target) {
        int left = -1, right = nums.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] <= target
            // nums[right] > target
            int mid = (left + right) >>> 1; // 比 left+(right-left)/2 更快的写法
            if (nums[mid] >= target) {
                right = mid; // 二分范围缩小到 (left, mid)
            } else {
                left = mid; // 二分范围缩小到 (mid, right)
            }
        }
        return right;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        ranges::sort(potions);
        for (int& x : spells) { // 原地修改
            x = potions.end() - ranges::lower_bound(potions, 1.0 * success / x);
        }
        return spells;
    }
};

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

// 返回 nums 中的第一个大于等于 target 的元素下标
int lowerBound(int* nums, int numsSize, double target) {
    int left = -1, right = numsSize; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid; // 二分范围缩小到 (left, mid)
        } else {
            left = mid; // 二分范围缩小到 (mid, right)
        }
    }
    return right;
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    qsort(potions, potionsSize, sizeof(int), cmp);
    for (int i = 0; i < spellsSize; i++) {
        spells[i] = potionsSize - lowerBound(potions, potionsSize, 1.0 * success / spells[i]);
    }
    *returnSize = spellsSize;
    return spells;
}

func successfulPairs(spells, potions []int, success int64) []int {
    slices.Sort(potions)
    for i, x := range spells {
        target := float64(success) / float64(x)
        j := sort.Search(len(potions), func(j int) bool { return float64(potions[j]) >= target })
        spells[i] = len(potions) - j
    }
    return spells
}

var successfulPairs = function(spells, potions, success) {
    potions.sort((a, b) => a - b);
    for (let i = 0; i < spells.length; i++) {
        const target = success / spells[i];
        spells[i] = potions.length - lowerBound(potions, target);
    }
    return spells;
};

var lowerBound = function(nums, target) {
    let left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < target
        // nums[right] >= target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid; // 范围缩小到 (left, mid)
        } else {
            left = mid; // 范围缩小到 (mid, right)
        }
    }
    return right;
}

var successfulPairs = function(spells, potions, success) {
    potions.sort((a, b) => a - b);
    for (let i = 0; i < spells.length; i++) {
        const target = success / spells[i];
        spells[i] = potions.length - _.sortedIndex(potions, target);
    }
    return spells;
};

impl Solution {
    pub fn successful_pairs(mut spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
        potions.sort_unstable();
        let last = potions[potions.len() - 1] as i64;
        for x in spells.iter_mut() {
            let target = success as f64 / *x as f64;
            let j = potions.partition_point(|&x| (x as f64) < target);
            *x = (potions.len() - j) as i32;
        }
        spells
    }
}

写法二：不使用浮点数

浮点数有舍入误差，如果数据范围更大，上面的做法就不一定正确了。

更好的做法是，避免使用浮点数，只使用整数计算。一方面可以保证正确性，另一方面整数运算比浮点运算快。

对于正整数，$xy\ge\textit{success}$ 等价于 $y\ge\left\lceil\dfrac{\textit{success}}{x}\right\rceil$。

为方便二分，可以利用如下恒等式：

$$
\left\lceil\dfrac{a}{b}\right\rceil = \left\lfloor\dfrac{a+b-1}{b}\right\rfloor = \left\lfloor\dfrac{a-1}{b}\right\rfloor + 1
$$

证明见 上取整下取整转换公式的证明。

根据上式，我们有

$$
y\ge\left\lceil\dfrac{\textit{success}}{x}\right\rceil = \left\lfloor\dfrac{\textit{success}-1}{x}\right\rfloor + 1
$$

也可以写成

$$
y>\left\lfloor\dfrac{\textit{success}-1}{x}\right\rfloor
$$

为什么不等式一定要这样变形？好处是只需要在二分之前做一次除法，避免在二分循环内计算乘法，效率更高。另外的好处是部分语言可以直接调用库函数二分。

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        success -= 1  # 提前减一，避免在循环中反复减一
        return [m - bisect_right(potions, success // x) for x in spells]

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        for (int i = 0; i < spells.length; i++) {
            long target = (success - 1) / spells[i];
            if (target < potions[potions.length - 1]) {
                // 这样写每次二分就只用比两个 int 的大小，避免把 potions 中的元素转成 long 比较
                spells[i] = potions.length - upperBound(potions, (int) target);
            } else {
                spells[i] = 0;
            }
        }
        return spells;
    }

    // 返回 nums 中的第一个大于 target 的元素下标
    private int upperBound(int[] nums, int target) {
        int left = -1, right = nums.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] <= target
            // nums[right] > target
            int mid = (left + right) >>> 1; // 比 left+(right-left)/2 更快的写法
            if (nums[mid] > target) {
                right = mid; // 二分范围缩小到 (left, mid)
            } else {
                left = mid; // 二分范围缩小到 (mid, right)
            }
        }
        return right;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        ranges::sort(potions);
        for (int& x : spells) { // 原地修改
            long long target = (success - 1) / x;
            if (target < potions.back()) {
                // 这样写每次二分就只用比两个 int 的大小，避免把 potions 中的元素转成 long long 比较
                x = potions.end() - ranges::upper_bound(potions, (int) target);
            } else {
                x = 0;
            }
        }
        return spells;
    }
};

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

// 返回 nums 中的第一个大于 target 的元素下标
int upperBound(int* nums, int numsSize, int target) {
    int left = -1, right = numsSize; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid; // 二分范围缩小到 (left, mid)
        } else {
            left = mid; // 二分范围缩小到 (mid, right)
        }
    }
    return right;
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    qsort(potions, potionsSize, sizeof(int), cmp);
    for (int i = 0; i < spellsSize; i++) {
        long long target = (success - 1) / spells[i];
        if (target < potions[potionsSize - 1]) {
            // 这样写每次二分就只用比两个 int 的大小，避免把 potions 中的元素转成 long long 比较
            spells[i] = potionsSize - upperBound(potions, potionsSize, target);
        } else {
            spells[i] = 0;
        }
    }
    *returnSize = spellsSize;
    return spells;
}

func successfulPairs(spells, potions []int, success int64) []int {
slices.Sort(potions)
for i, x := range spells {
spells[i] = len(potions) - sort.SearchInts(potions, (int(success)-1)/x+1)
}
return spells
}

var successfulPairs = function(spells, potions, success) {
    potions.sort((a, b) => a - b);
    for (let i = 0; i < spells.length; i++) {
        const target = Math.ceil(success / spells[i]);
        spells[i] = potions.length - lowerBound(potions, target);
    }
    return spells;
};

var lowerBound = function(nums, target) {
    let left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < target
        // nums[right] >= target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid; // 范围缩小到 (left, mid)
        } else {
            left = mid; // 范围缩小到 (mid, right)
        }
    }
    return right;
}

var successfulPairs = function(spells, potions, success) {
    potions.sort((a, b) => a - b);
    for (let i = 0; i < spells.length; i++) {
        const target = Math.ceil(success / spells[i]);
        spells[i] = potions.length - _.sortedIndex(potions, target);
    }
    return spells;
};

impl Solution {
    pub fn successful_pairs(mut spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
        potions.sort_unstable();
        let last = potions[potions.len() - 1] as i64;
        for x in spells.iter_mut() {
            let target = (success - 1) / *x as i64;
            if target < last { // 防止 i64 转成 i32 截断（这样不需要把 potions 中的数转成 i64 比较）
                let j = potions.partition_point(|&x| x <= target as i32);
                *x = (potions.len() - j) as i32;
            } else {
                *x = 0;
            }
        }
        spells
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}((n+m)\log m)$，其中 $n$ 为 $\textit{spells}$ 的长度，$m$ 为 $\textit{potions}$ 的长度。排序 $\mathcal{O}(m\log m)$。二分 $n$ 次，每次 $\mathcal{O}(\log m)$。
• 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销，仅用到若干额外变量。

方法二：计数 + 值域后缀和

方法一得出的结论是，统计满足 $\textit{potions}[j]\ge \left\lfloor\dfrac{\textit{success}-1}{\textit{spell}[i]}\right\rfloor + 1$ 的药水的个数。

比如 $\textit{potions}=[1,2,2,3,5,5,5]$，要计算 $\ge 2$ 的药水的个数，我们可以统计每个数出现了多少次，记在一个 $\textit{cnt}$ 数组中。在这个例子中，$\textit{cnt}=[0,1,2,1,0,3]$，比如 $\textit{cnt}[5]=3$ 表示 $5$ 出现了 $3$ 次。

那么计算 $\textit{cnt}[2] + \textit{cnt}[3] + \textit{cnt}[4] + \textit{cnt}[5]=2+1+0+3=6$，就是 $\ge 2$ 的药水的个数。

但这样太慢了。如何加速？

借鉴 前缀和 的思想，我们可以倒着遍历 $\textit{cnt}$，原地计算 $\textit{cnt}$ 的后缀和，把 $\textit{cnt}[i]$ 更新为 $\ge i$ 的药水的个数。上面的 $\textit{cnt}$ 可以更新为 $[7,7,6,4,3,3]$。比如 $\textit{cnt}[2] = 6$ 表示 $\ge 2$ 的药水的个数。

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        mx = max(potions)
        cnt = [0] * (mx + 1)
        for y in potions:
            cnt[y] += 1  # 统计每种药水的出现次数

        # 计算 cnt 的后缀和
        for i in range(mx - 1, -1, -1):
            cnt[i] += cnt[i + 1]
        # 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

        for i, x in enumerate(spells):
            low = (success - 1) // x + 1
            spells[i] = cnt[low] if low <= mx else 0
        return spells

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int mx = 0;
        for (int y : potions) {
            mx = Math.max(mx, y);
        }

        int[] cnt = new int[mx + 1];
        for (int y : potions) {
            cnt[y]++; // 统计每种药水的出现次数
        }

        // 计算 cnt 的后缀和
        for (int i = mx - 1; i >= 0; i--) {
            cnt[i] += cnt[i + 1];
        }
        // 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

        for (int i = 0; i < spells.length; i++) {
            long low = (success - 1) / spells[i] + 1;
            spells[i] = low <= mx ? cnt[(int) low] : 0;
        }
        return spells;
    }
}

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int mx = ranges::max(potions);
        vector<int> cnt(mx + 1);
        for (int y : potions) {
            cnt[y]++; // 统计每种药水的出现次数
        }

        // 计算 cnt 的后缀和
        for (int i = mx - 1; i >= 0; i--) {
            cnt[i] += cnt[i + 1];
        }
        // 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

        for (int& x : spells) {
            long long low = (success - 1) / x + 1;
            x = low <= mx ? cnt[low] : 0;
        }
        return spells;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    int mx = 0;
    for (int i = 0; i < potionsSize; i++) {
        mx = MAX(mx, potions[i]);
    }

    int* cnt = calloc(mx + 1, sizeof(int));
    for (int i = 0; i < potionsSize; i++) {
        cnt[potions[i]]++; // 统计每种药水的出现次数
    }

    // 计算 cnt 的后缀和
    for (int i = mx - 1; i >= 0; i--) {
        cnt[i] += cnt[i + 1];
    }
    // 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

    for (int i = 0; i < spellsSize; i++) {
        long long low = (success - 1) / spells[i] + 1;
        spells[i] = low <= mx ? cnt[low] : 0;
    }

    *returnSize = spellsSize;
    free(cnt);
    return spells;
}

func successfulPairs(spells, potions []int, success int64) []int {
mx := slices.Max(potions)
cnt := make([]int, mx+1)
for _, y := range potions {
cnt[y]++ // 统计每种药水的出现次数
}

// 计算 cnt 的后缀和
for i := mx - 1; i >= 0; i-- {
cnt[i] += cnt[i+1]
}
// 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

for i, x := range spells {
low := (int(success)-1)/x + 1
if low <= mx {
spells[i] = cnt[low]
} else {
spells[i] = 0
}
}
return spells
}

var successfulPairs = function(spells, potions, success) {
    const mx = Math.max(...potions);
    const cnt = Array(mx + 1).fill(0);
    for (const y of potions) {
        cnt[y]++; // 统计每种药水的出现次数
    }

    // 计算 cnt 的后缀和
    for (let i = mx - 1; i >= 0; i--) {
        cnt[i] += cnt[i + 1];
    }
    // 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

    for (let i = 0; i < spells.length; i++) {
        const low = Math.ceil(success / spells[i]);
        spells[i] = low <= mx ? cnt[low] : 0;
    }
    return spells;
};

impl Solution {
    pub fn successful_pairs(mut spells: Vec<i32>, potions: Vec<i32>, success: i64) -> Vec<i32> {
        let mx = *potions.iter().max().unwrap() as usize;
        let mut cnt = vec![0; mx + 1];
        for y in potions {
            cnt[y as usize] += 1; // 统计每种药水的出现次数
        }

        // 计算 cnt 的后缀和
        for i in (0..mx).rev() {
            cnt[i] += cnt[i + 1];
        }
        // 计算完毕后，cnt[i] 就是 potions 值 >= i 的药水个数

        let success = success as usize;
        for x in spells.iter_mut() {
            let low = (success - 1) / *x as usize + 1;
            *x = if low <= mx { cnt[low] } else { 0 };
        }
        spells
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n+m+U)$，其中 $n$ 为 $\textit{spells}$ 的长度，$m$ 为 $\textit{potions}$ 的长度，$U=\max(\textit{potions})$。
• 空间复杂度：$\mathcal{O}(U)$。

思考题

把乘法改成异或要怎么做？

这题是 1803. 统计异或值在范围内的数对有多少，做法见 我的题解。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。如果第 n 个湖泊下雨前是 满的 ，这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。

给你一个整数数组 rains ，其中：

• rains[i] > 0 表示第 i 天时，第 rains[i] 个湖泊会下雨。
• rains[i] == 0 表示第 i 天没有湖泊会下雨，你可以选择 一个 湖泊并 抽干 这个湖泊的水。

请返回一个数组 ans ，满足：

• ans.length == rains.length
• 如果 rains[i] > 0 ，那么ans[i] == -1 。
• 如果 rains[i] == 0 ，ans[i] 是你第 i 天选择抽干的湖泊。

如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。

请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。

示例 1：

输入：rains = [1,2,3,4]
输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。

示例 2：

输入：rains = [1,2,0,0,2,1]
输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

示例 3：

输入：rains = [1,2,0,1,2]
输出：[]
解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。

提示：

• 1 <= rains.length <= 105
• 0 <= rains[i] <= 109

第一个错误的思路

从左到右遍历 $\textit{rains}$：

• 如果 $\textit{rains}[i]=0$，把 $i$ 加到一个列表中，后面要抽水的时候再使用。
• 如果 $\textit{rains}[i]>0$ 且 $\textit{rains}[i]$ 是满的，随便取出列表中的一天用来抽水。如果列表是空的，那么必定会发生洪水。

错误原因：比如 $\textit{rains}=[1,0,0,1,1]$，抽水之后连着下了两天的雨，最后一天必定发洪水。注意抽水必须在两个 $1$ 之间，第二个 $0$ 无法用来抽干湖水。但按照上面的算法，我们会错误地认为第二个 $0$ 可以把湖 $1$ 抽干。

第二个错误的思路

从左到右遍历 $\textit{rains}$：

• 如果 $\textit{rains}[i]=0$，把 $i$ 入栈。
• 如果 $\textit{rains}[i]>0$ 且 $\textit{rains}[i]$ 是满的，那么用栈顶的那一天抽水。如果栈顶那一天比 $\textit{rains}[i]$ 装满的那一天还要早，那么必定会发生洪水。

错误原因：例如 $\textit{rains}=[1,0,2,0,1,2]$，如果第二个 $0$ 用来抽湖 $1$，那么湖 $2$ 就没法抽干。

正确思路

从左到右遍历 $\textit{rains}$：

• 如果 $\textit{rains}[i]=0$，把 $i$ 加到一个有序集合中。
• 如果 $\textit{rains}[i]>0$ 且 $\textit{rains}[i]$ 是满的。设 $\textit{rains}[i]$ 装满的那一天为 $j$，从有序集合中选出大于 $j$ 的最早的抽水日。

解释：越晚的抽水日，灵活性越大，可以用于更晚装满的湖。所以越晚的抽水日越应该留到后面再使用。

写法一：有序集合

###py

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [-1] * n
        full_day = {}  # lake -> 装满日
        dry_day = SortedList()  # 未被使用的抽水日
        for i, lake in enumerate(rains):
            if lake == 0:
                ans[i] = 1  # 先随便选一个湖抽干
                dry_day.add(i)  # 保存抽水日
                continue
            if lake in full_day:
                j = full_day[lake]
                # 必须在 j 之后，i 之前把 lake 抽干
                # 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                k = dry_day.bisect_right(j)
                if k == len(dry_day):
                    return []  # 无法阻止洪水
                d = dry_day[k]
                ans[d] = lake
                dry_day.discard(d)  # 移除已使用的抽水日
            full_day[lake] = i  # 插入或更新装满日
        return ans

###java

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] ans = new int[n];
        Map<Integer, Integer> fullDay = new HashMap<>(); // lake -> 装满日
        TreeSet<Integer> dryDay = new TreeSet<>(); // 未被使用的抽水日
        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            if (lake == 0) {
                ans[i] = 1; // 先随便选一个湖抽干
                dryDay.add(i); // 保存抽水日
                continue;
            }
            Integer j = fullDay.get(lake);
            if (j != null) {
                // 必须在 j 之后，i 之前把 lake 抽干
                // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                Integer d = dryDay.higher(j);
                if (d == null) {
                    return new int[]{}; // 无法阻止洪水
                }
                ans[d] = lake;
                dryDay.remove(d); // 移除已使用的抽水日
            }
            ans[i] = -1;
            fullDay.put(lake, i); // 插入或更新装满日
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n, -1);
        unordered_map<int, int> full_day; // lake -> 装满日
        set<int> dry_day; // 未被使用的抽水日
        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            if (lake == 0) {
                ans[i] = 1; // 先随便选一个湖抽干
                dry_day.insert(i); // 保存抽水日
                continue;
            }
            if (full_day.contains(lake)) {
                int j = full_day[lake];
                // 必须在 j 之后，i 之前把 lake 抽干
                // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                auto it = dry_day.upper_bound(j);
                if (it == dry_day.end()) {
                    return {}; // 无法阻止洪水
                }
                ans[*it] = lake;
                dry_day.erase(it); // 移除已使用的抽水日
            }
            full_day[lake] = i; // 插入或更新装满日
        }
        return ans;
    }
};

###go

// import "github.com/emirpasic/gods/v2/trees/redblacktree"
func avoidFlood(rains []int) []int {
ans := make([]int, len(rains))
fullDay := map[int]int{} // lake -> 装满日
dryDay := redblacktree.New[int, struct{}]() // 未被使用的抽水日
for i, lake := range rains {
if lake == 0 {
ans[i] = 1 // 先随便选一个湖抽干
dryDay.Put(i, struct{}{}) // 保存抽水日
continue
}
if j, ok := fullDay[lake]; ok {
// 必须在 j 之后，i 之前把 lake 抽干
// 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
node, _ := dryDay.Ceiling(j)
if node == nil {
return nil // 无法阻止洪水
}
ans[node.Key] = lake
dryDay.Remove(node.Key) // 移除已使用的抽水日
}
ans[i] = -1
fullDay[lake] = i // 插入或更新装满日
}
return ans
}

###js

const { AvlTree } = require('datastructures-js');

var avoidFlood = function(rains) {
    const n = rains.length;
    const ans = Array(n).fill(-1);
    const fullDay = new Map(); // lake -> 装满日
    const dryDay = new AvlTree((a, b) => a - b); // 未被使用的抽水日
    for (let i = 0; i < n; i++) {
        const lake = rains[i];
        if (lake === 0) {
            ans[i] = 1; // 先随便选一个湖抽干
            dryDay.insert(i); // 保存抽水日
            continue;
        }
        const j = fullDay.get(lake);
        if (j !== undefined) {
            // 必须在 j 之后，i 之前把 lake 抽干
            // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
            const node = dryDay.ceil(j);
            if (node === null) {
                return []; // 无法阻止洪水
            }
            ans[node.getValue()] = lake;
            dryDay.removeNode(node); // 移除已使用的抽水日
        }
        fullDay.set(lake, i); // 插入或更新装满日
    }
    return ans;
};

###rust

use std::collections::{BTreeSet, HashMap};

impl Solution {
    pub fn avoid_flood(rains: Vec<i32>) -> Vec<i32> {
        let n = rains.len();
        let mut ans = vec![-1; n];
        let mut full_day = HashMap::new(); // lake -> 装满日
        let mut dry_day = BTreeSet::new(); // 未被使用的抽水日
        for (i, lake) in rains.into_iter().enumerate() {
            if lake == 0 {
                ans[i] = 1; // 先随便选一个湖抽干
                dry_day.insert(i); // 保存抽水日
                continue;
            }
            if let Some(&j) = full_day.get(&lake) {
                // 必须在 j 之后，i 之前把 lake 抽干
                // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                if let Some(&d) = dry_day.range(j..).next() {
                    ans[d] = lake;
                    dry_day.remove(&d); // 移除已使用的抽水日
                } else {
                    return vec![]; // 无法阻止洪水
                }
            }
            full_day.insert(lake, i); // 插入或更新装满日
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{rains}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

写法二：并查集

删除 $i$ 时，用并查集把 $i$ 指向 $i+1$（或者 $\text{find}(i+1)$）。

例如删除 $2$，那么并查集中 $2\to 3$。

然后删除 $3$，那么并查集中 $2\to 3\to 4$。

查找 $\ge 2$ 的最小的未被删除的天，顺着并查集中的 $2$，可以找到 $4$，即为 $\ge 2$ 的最小的未被删除的天。

对于 $\textit{rains}[i]>0$ 的天，直接把 $i$ 删除。

注：关于并查集的完整模板，见 数据结构题单。

###py

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        # 非递归并查集
        fa = list(range(n + 1))
        def find(x: int) -> int:
            rt = x
            while fa[rt] != rt:
                rt = fa[rt]
            while fa[x] != rt:
                fa[x], x = rt, fa[x]
            return rt

        ans = [-1] * n
        full_day = {}  # lake -> 装满日
        for i, lake in enumerate(rains):
            if lake == 0:
                ans[i] = 1  # 先随便选一个湖抽干
                continue
            if lake in full_day:
                j = full_day[lake]
                # 必须在 j 之后，i 之前把 lake 抽干
                # 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                dry_day = find(j + 1)
                if dry_day >= i:
                    return []  # 无法阻止洪水
                ans[dry_day] = lake
                fa[dry_day] = find(dry_day + 1)  # 删除 dry_day
            fa[i] = i + 1  # 删除 i
            full_day[lake] = i  # 插入或更新装满日
        return ans

###java

class Solution {
    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] fa = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
        }

        int[] ans = new int[n];
        Map<Integer, Integer> fullDay = new HashMap<>(); // lake -> 装满日
        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            if (lake == 0) {
                ans[i] = 1; // 先随便选一个湖抽干
                continue;
            }
            Integer j = fullDay.get(lake);
            if (j != null) {
                // 必须在 j 之后，i 之前把 lake 抽干
                // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                int dryDay = find(j + 1, fa);
                if (dryDay >= i) {
                    return new int[]{}; // 无法阻止洪水
                }
                ans[dryDay] = lake;
                fa[dryDay] = find(dryDay + 1, fa); // 删除 dryDay
            }
            ans[i] = -1;
            fa[i] = i + 1; // 删除 i
            fullDay.put(lake, i); // 插入或更新装满日
        }
        return ans;
    }

    private int find(int x, int[] fa) {
        if (fa[x] != x) {
            fa[x] = find(fa[x], fa);
        }
        return fa[x];
    }
}

###cpp

class Solution {
    vector<int> fa;

    int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        fa.resize(n + 1);
        ranges::iota(fa, 0); // 并查集初始化

        vector<int> ans(n, -1);
        unordered_map<int, int> full_day; // lake -> 装满日
        for (int i = 0; i < n; i++) {
            int lake = rains[i];
            if (lake == 0) {
                ans[i] = 1; // 先随便选一个湖抽干
                continue;
            }
            if (full_day.count(lake)) {
                int j = full_day[lake];
                // 必须在 j 之后，i 之前把 lake 抽干
                // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
                int dry_day = find(j + 1);
                if (dry_day >= i) {
                    return {}; // 无法阻止洪水
                }
                ans[dry_day] = lake;
                fa[dry_day] = find(dry_day + 1); // 删除 dry_day
            }
            fa[i] = i + 1; // 删除 i
            full_day[lake] = i; // 插入或更新装满日
        }
        return ans;
    }
};

###go

func avoidFlood(rains []int) []int {
n := len(rains)
// 非递归并查集
fa := make([]int, n+1)
for i := range fa {
fa[i] = i
}
find := func(x int) int {
rt := x
for fa[rt] != rt {
rt = fa[rt]
}
for fa[x] != rt {
fa[x], x = rt, fa[x]
}
return rt
}

ans := make([]int, n)
fullDay := map[int]int{} // lake -> 装满日
for i, lake := range rains {
if lake == 0 {
ans[i] = 1 // 先随便选一个湖抽干
continue
}
if j, ok := fullDay[lake]; ok {
// 必须在 j 之后，i 之前把 lake 抽干
// 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
dryDay := find(j + 1)
if dryDay >= i {
return nil // 无法阻止洪水
}
ans[dryDay] = lake
fa[dryDay] = find(dryDay + 1) // 删除 dryDay
}
ans[i] = -1
fa[i] = i + 1 // 删除 i
fullDay[lake] = i // 插入或更新装满日
}
return ans
}

###js

var avoidFlood = function(rains) {
    const n = rains.length;
    const fa = Array(n + 1).fill(0).map((_, i) => i);

    function find(x) {
        if (fa[x] !== x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

    const ans = Array(n).fill(-1);
    const fullDay = new Map(); // lake -> 装满日
    for (let i = 0; i < n; i++) {
        const lake = rains[i];
        if (lake === 0) {
            ans[i] = 1; // 先随便选一个湖抽干
            continue;
        }
        const j = fullDay.get(lake);
        if (j !== undefined) {
            // 必须在 j 之后，i 之前把 lake 抽干
            // 选一个最早的未被使用的抽水日，如果选晚的，可能会导致其他湖没有可用的抽水日
            const dryDay = find(j + 1);
            if (dryDay >= i) {
                return []; // 无法阻止洪水
            }
            ans[dryDay] = lake;
            fa[dryDay] = find(dryDay + 1); // 删除 dryDay
        }
        fa[i] = i + 1; // 删除 i
        fullDay.set(lake, i); // 插入或更新装满日
    }
    return ans;
};

###rust

use std::collections::HashMap;

impl Solution {
    pub fn avoid_flood(rains: Vec<i32>) -> Vec<i32> {
        let n = rains.len();
        let mut fa = (0..=n).collect::<Vec<_>>();

        fn find(x: usize, fa: &mut [usize]) -> usize {
            if fa[x] != x {
                fa[x] = find(fa[x], fa);
            }
            fa[x]
        }

        let mut ans = vec![-1; n];
        let mut full_day = HashMap::new(); // lake -> 装满日
        for (i, lake) in rains.into_iter().enumerate() {
            if lake == 0 {
                ans[i] = 1; // 先随便选一个湖抽干
                continue;
            }
            if let Some(&j) = full_day.get(&lake) {
                // 必须在 j 之后，i 之前把 lake 抽干
                let dry_day = find(j + 1, &mut fa);
                if dry_day >= i {
                    return vec![]; // 无法阻止洪水
                }
                ans[dry_day] = lake;
                fa[dry_day] = find(dry_day + 1, &mut fa); // 删除 dry_day
            }
            fa[i] = i + 1; // 删除 i
            full_day.insert(lake, i); // 插入或更新装满日
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{rains}$ 的长度。本题并查集的操作是均摊 $\mathcal{O}(1)$。
• 空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面数据结构题单的「§7.4 数组上的并查集」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府