2026-10-29：击败所有怪物的最小初始强度。用go语言，给定一个整数数组 monsters，其中每个元素代表对应怪物的强度。另有二维数组 boosts

2026-10-29：击败所有怪物的最小初始强度。用go语言，给定一个整数数组 monsters，其中每个元素代表对应怪物的强度。另有二维数组 boosts，每一项写成 [li, ri, vi]，含义是：当你要对付编号位于 li 到 ri 区间内的怪物时，会获得 vi 点临时增益；多个区间同时覆盖某个怪物时，这些增益值累加。

你的初始体力是一个非负整数。你需要按照从左到右的顺序逐个与怪物交战。对第 i 个怪物，先计算所有覆盖它的增益值总和，记为 bonus。只有当前体力加上 bonus 不小于该怪物的强度时，才能打赢它。打赢后，当前体力减去该怪物强度；如果结果小于 0，则把体力记为 0。临时增益只用于判断这一战能否获胜，不会改变你的体力数值。

请计算：为了让所有怪物都能按顺序被击败，初始体力最低可以取多少。

1 <= monsters.length <= 5 * 10000。

1 <= monsters[i] <= 1000000000。

0 <= boosts.length <= 5 * 10000。

boosts[i] == [li, ri, vi]。

0 <= li <= ri < monsters.length。

1 <= vi <= 1000000000。

输入： monsters = [5,10,15], boosts = [[1,1,10]]。

输出： 30。

解释：

让我们以 30 的初始强度开始。

monsters[0] = 5：在下标 0 处，加成为 0。由于 30 + 0 >= 5，该怪物可以被击败。强度变为 30 - 5 = 25。

monsters[1] = 10：在下标 1 处，加成为 10。由于 25 + 10 >= 10，该怪物可以被击败。强度变为 25 - 10 = 15。

monsters[2] = 15：在下标 2 处，加成为 0。由于 15 + 0 >= 15，该怪物可以被击败。强度变为 15 - 15 = 0。

因此，所需的最小初始强度是 30。

题目来自离开4008。

大体步骤如下：

一、准备每个怪物对应的临时加成

1. 1. 先取怪物数量 n，创建一个长度为 n+1 的数组，用来记录“加成差分”。这个数组的每个位置一开始都是 0。

2. 2. 遍历所有加成区间。对于每个区间 [li, ri, vi]，做两件事：

• • 在差分数组的 li 位置加上 vi，表示从 li 开始这个增益生效；

• • 在差分数组的 ri+1 位置减去 vi，表示从 ri+1 开始这个增益失效。
  这样处理多个区间重叠时，后续通过前缀和就能自然把重叠区间的增益累加起来。

3. 对差分数组从下标 1 到 n-1 做前缀和。前缀和完成后，数组中下标 i 的值就是怪物 i 实际能获得的全部临时加成 bonus[i]。
注意：代码中差分数组长度是 n+1，但前缀和只处理到 n-1，因为真正需要使用的加成只对应怪物下标 0 到 n-1。

二、从右往左寻找决定答案的怪物

1. 1. 从最后一个怪物下标 n-1 开始，向左逐个扫描。

2. 2. 对每个下标 i，比较 monsters[i] 和 bonus[i]。

• • 如果 monsters[i] 大于 bonus[i]，说明仅靠临时加成还不够，必须让当前体力至少补上差额 monsters[i] - bonus[i]，否则这个怪物无法击败。

• • 如果 monsters[i] 小于或等于 bonus[i]，说明即使当前体力为 0，仅靠加成也能击败它，因此这个位置不会对初始体力提出额外要求。

3. 代码从右往左找第一个满足 monsters[i] > bonus[i] 的位置。一旦找到，就立即计算答案并返回。
原因是：对于满足 monsters[i] > bonus[i] 的位置，越靠右，前面累计消耗的怪物总强度越大；并且该位置本身还需要补足 monsters[i] - bonus[i] 的差额。由于 bonus 是非负的，且该位置满足差额为正，所以越靠右的这类位置对初始体力的要求不会更小。因此最后一个“必须靠已有体力补足”的怪物决定了最小初始体力。
如果整个数组都不存在 monsters[i] > bonus[i] 的位置，说明每个怪物都能靠临时加成在体力为 0 时通过，因此最小初始体力就是 0，代码返回 0。

三、计算并返回最小初始体力

1. 1. 当找到满足条件的位置 i 后，代码先令答案等于负的 bonus[i]，即从“减去这个位置的加成”开始。

2. 2. 然后遍历 monsters 从下标 0 到 i 的所有怪物，把这些怪物的强度全部累加。

3. 3. 最终答案就是：前面 0 到 i 这些怪物的总强度，再减去怪物 i 获得的临时加成 bonus[i]。
   直观理解是：要打到第 i 个怪物时，前面这些怪物总共会消耗掉相应体力；而第 i 个怪物有 bonus[i] 的临时加成，所以初始体力至少要等于“累计总消耗减去这个加成”。

4. 4. 返回该结果。代码最后把结果转成 64 位整数返回，因为怪物强度和加成可能很大，累计值可能超过 32 位整数范围。

四、结合示例说明
示例中 monsters = [5,10,15]，boosts = [[1,1,10]]。

1. 1. 差分数组初始全为 0。处理区间 [1,1,10] 后，在下标 1 加 10，在下标 2 减 10。

2. 2. 做前缀和后，怪物 0 的加成为 0，怪物 1 的加成为 10，怪物 2 的加成为 0。

3. 3. 从右往左扫描：

• • 下标 2：monsters[2] = 15，bonus[2] = 0，15 大于 0，满足条件。

4. 计算答案：把 monsters[0] 到 monsters[2] 全部相加，得到 5 + 10 + 15 = 30；再减去 bonus[2] = 0，得到 30。

5. 返回 30，与题目输出一致。
实际战斗过程也验证了：初始 30 时，打完第一个剩 25；第二个有 10 点加成，25 + 10 >= 10，打完剩 15；第三个无加成，15 >= 15，打完剩 0。

五、复杂度分析
设怪物数量为 n，加成区间数量为 m。

1. 1. 时间复杂度：

• • 处理所有 boosts 建立差分数组需要 O(m)；

• • 对差分数组做前缀和需要 O(n)；

• • 从右往左扫描怪物需要 O(n)；

• • 找到位置后累加 monsters[0..i] 最坏需要 O(n)。
  因此总时间复杂度为 O(n + m)，也就是关于怪物数量和加成区间数量线性。

2. 额外空间复杂度：

• • 主要额外空间是长度为 n+1 的加成差分/前缀和数组，需要 O(n)。

• • 其余变量都是常量级。
  因此总额外空间复杂度为 O(n)。

package main

 import (
    "fmt"
)

 func minInitialStrength(monsters []int, boosts [][]int)int64 {
    n := len(monsters)
    bonus := make([]int, n+1)
    for _, b := range boosts {
        bonus[b[0]] += b[2]
        bonus[b[1]+1] -= b[2]
    }

     // 差分数组的前缀和即原数组
    for i := 1; i < n; i++ {
        bonus[i] += bonus[i-1]
    }

     for i := n - 1; i >= 0; i-- {
        if monsters[i] > bonus[i] {
            ans := -bonus[i]
            for _, x := range monsters[:i+1] {
                ans += x
            }
            returnint64(ans)
        }
    }
    return0
}

 func main() {
    monsters := []int{5, 10, 15}
    boosts := [][]int{{1, 1, 10}}
    result := minInitialStrength(monsters, boosts)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def min_initial_strength(monsters: list[int], boosts: list[list[int]]) -> int:
    n = len(monsters)
    bonus = [0] * (n + 1)

     # 用差分数组记录每个位置获得的加成
    for b in boosts:
        bonus[b[0]] += b[2]
        bonus[b[1] + 1] -= b[2]

     # 差分数组前缀和，得到每个位置的累计加成
    for i in range(1, n):
        bonus[i] += bonus[i - 1]

     # 从右往左找第一个 monsters[i] > bonus[i] 的位置
    for i in range(n - 1, -1, -1):
        if monsters[i] > bonus[i]:
            ans = -bonus[i]
            ans += sum(monsters[:i + 1])
            return ans

     return0

 if __name__ == "__main__":
    monsters = [5, 10, 15]
    boosts = [[1, 1, 10]]
    result = min_initial_strength(monsters, boosts)
    print(result)

C++完整代码如下：

  

  


 using namespace std;

 long long minInitialStrength(vector monsters, vector 
 
 int 
 >> boosts) { 
 
 
      
 int 
  n = monsters.size(); 
 
 
     vector 
 
 bonus(n +  
 
 1 
 ,  
 0 
 ); 
 
 
 
 
      
 // 用差分数组记录每个位置获得的加成 
 
 
      
 for 
  ( 
 const 
  auto& b : boosts) { 
 
 
         bonus[b[ 
 0 
 ]] += b[ 
 2 
 ]; 
 
 
         bonus[b[ 
 1 
 ] +  
 1 
 ] -= b[ 
 2 
 ]; 
 
 
     } 
 
 
 
 
      
 // 差分数组前缀和，得到每个位置的累计加成 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < n; i++) { 
 
 
         bonus[i] += bonus[i -  
 1 
 ]; 
 
 
     } 
 
 
 
 
      
 // 从右往左找第一个 monsters[i] > bonus[i] 的位置 
 
 
      
 for 
  ( 
 int 
  i = n -  
 1 
 ; i >=  
 0 
 ; i--) { 
 
 
          
 if 
  (monsters[i] > bonus[i]) { 
 
 
             long long ans = -bonus[i]; 
 
 
              
 for 
  ( 
 int 
  j =  
 0 
 ; j <= i; j++) { 
 
 
                 ans += monsters[j]; 
 
 
             } 
 
 
              
 return 
  ans; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > monsters = { 
 5 
 ,  
 10 
 ,  
 15 
 }; 
 
 
     vector 
 
 int 
 >> boosts = {{ 
 1 
 ,  
 1 
 ,  
 10 
 }}; 
 
 
 
 
     long long result = minInitialStrength(monsters, boosts); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。