How do I calculate the minimum training hours for each opponent?

You need to compare your current energy and experience with the opponent’s requirements and calculate how much additional training is needed to exceed both values.

What is the greedy strategy for this problem?

The greedy strategy involves increasing either energy or experience first based on which one is lagging behind the opponent’s requirements, ensuring you defeat opponents with minimal training.

What is the importance of updating both energy and experience?

After each opponent, you need to update both energy and experience as defeating an opponent increases your experience and energy, which can help in defeating future opponents.

How does the training process affect future opponents?

Each opponent you defeat increases your energy and experience, which makes it easier to defeat subsequent opponents. So, managing the training effectively is key to minimizing the total hours.

Can this problem be solved without a greedy approach?

While the greedy approach is the most efficient, it is possible to approach this problem with a more exhaustive simulation. However, that would result in a higher time complexity.

#2383

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

赢得比赛需要的最少训练时长

你正在参加一场比赛，给你两个正整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。另给你两个下标从 0 开始的整数数组 energy 和 experience ，长度均为 n 。你将会依次对上 n 个对手。第 i 个对手的精力和经验分…

数组贪心

题目描述

你正在参加一场比赛，给你两个正整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会依次对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都严格超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验增加 experience[i]，但会将你的精力减少 energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者将精力增加 1 。

返回击败全部 n 个对手需要训练的最少小时数目。

示例 1：

输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出：8
解释：在 6 小时训练后，你可以将精力提高到 11 ，并且再训练 2 个小时将经验提高到 5 。
按以下顺序与对手比赛：
- 你的精力与经验都超过第 0 个对手，所以获胜。
  精力变为：11 - 1 = 10 ，经验变为：5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手，所以获胜。
  精力变为：10 - 4 = 6 ，经验变为：7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手，所以获胜。
  精力变为：6 - 3 = 3 ，经验变为：13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手，所以获胜。
  精力变为：3 - 2 = 1 ，经验变为：16 + 1 = 17 。
在比赛前进行了 8 小时训练，所以返回 8 。
可以证明不存在更小的答案。

示例 2：

输入：initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
输出：0
解释：你不需要额外的精力和经验就可以赢得比赛，所以返回 0 。

提示：

n == energy.length == experience.length
1 <= n <= 100
1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

lightbulb

解题思路

方法一：贪心 + 模拟

我们不妨记当前的精力为 $x$ ，经验为 $y$ 。

接下来，我们遍历每个对手，对于第 $i$ 个对手，记其精力为 $dx$ ，经验为 $dy$ 。

如果 $x \leq dx$ ，那么我们需要训练 $dx + 1 - x$ 小时，将精力提升到 $dx + 1$ ；
如果 $y \leq dy$ ，那么我们需要训练 $dy + 1 - y$ 小时，将经验提升到 $dy + 1$ ；
然后我们将精力减去 $dx$ ，经验加上 $dy$ 。

最后返回答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 为对手的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minNumberOfHours(
        self, x: int, y: int, energy: List[int], experience: List[int]
    ) -> int:
        ans = 0
        for dx, dy in zip(energy, experience):
            if x <= dx:
                ans += dx + 1 - x
                x = dx + 1
            if y <= dy:
                ans += dy + 1 - y
                y = dy + 1
            x -= dx
            y += dy
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate uses a greedy strategy to balance energy and experience.
question_mark
The candidate demonstrates an understanding of simulation techniques for tracking and updating energy/experience.
question_mark
The candidate applies a clear approach for calculating minimum training hours efficiently.

warning

常见陷阱

外企场景

error
Forgetting to update both energy and experience after each opponent.
error
Overestimating the amount of training needed—ensure that you only train as much as necessary to defeat the next opponent.
error
Ignoring the fact that increasing experience may help with defeating future opponents more easily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the energy and experience arrays were sorted in descending order of difficulty? This would change the approach slightly, as the order of opponents could affect the minimum training hours.
arrow_right_alt
What if you could train in increments other than 1 hour at a time? This could complicate the calculation of training hours, requiring a different greedy method or approach.
arrow_right_alt
What if you could train energy and experience together instead of separately? This would change how you calculate and balance the minimum training required.

help

常见问题

外企场景

继续练习

#2389 和有限的最长子序列 #2366 将数组排序的最少替换次数 #2406 将区间分为最少组数