2026-09-19：设备评分的最大和。用go语言，有一个 m 行 n 列的整数矩阵 units。每一行代表一台设备，行里的 n 个整数表示该设备各个单元

2026-09-19：设备评分的最大和。用go语言，有一个 m 行 n 列的整数矩阵 units。每一行代表一台设备，行里的 n 个整数表示该设备各个单元的容量。每台设备的得分等于它这一行中所有单元容量的最小值。

可以执行零次或多次下面的操作：挑一台此前没有作为输出方使用过的设备，从它里面取走一个单元，把这个单元放到另一台设备中；然后这台被取走单元的设备记为已使用，之后不能再被挑作输出方。接收单元的设备没有限制，可以接收多个单元，也可以本身已经作为输出方使用过。若某台设备没有任何单元，则它的得分为 0。

目标是经过任意次操作后，让所有设备的得分总和尽可能大，返回这个最大总和。

1 <= m == units.length <= 100000。

1 <= n == units[i].length <= 100000。

m * n <= 200000。

1 <= units[i][j] <= 100000。

输入： units = [[5,5,5],[1,1,1]]。

输出： 6。

解释：

没有任何转移能增加评分之和。因此，评分之和为 5 + 1 = 6。

题目来自力扣3961。

具体步骤如下：

1. 1. 先处理特殊情况：如果每台设备都只有一个单元，也就是矩阵的列数 n 等于 1。此时任何转移操作都不能增加任何设备的评分。因为设备只有一个单元，它的评分就是这个单元；如果把单元移走，该设备变空，评分为 0；接收设备的最小值也不会变大。所以最优做法是不做任何操作，直接把所有设备的唯一单元容量相加，结果就是最大评分之和。

2. 2. 对于一般情况，即每台设备至少有两个单元（n >= 2）：

• • 遍历每一台设备，找出这台设备所有单元中的最小值，记为“设备最小值”。

• • 同时找出这台设备所有单元中的次小值，记为“设备次小值”。注意，如果多个单元容量相同，次小值可以等于最小值。代码中的比较逻辑允许这种情况。

• • 先假设每台设备都执行一次操作：把自己的最小值移走。这样每台设备的评分就会从原来的最小值变成原来的次小值。

• • 把所有设备的次小值累加起来，得到一个临时总和。这个临时总和表示：如果所有设备都成功移走自己的最小值，并且暂时不考虑移走的单元放到了哪里，那么所有设备评分之和就是这些次小值之和。

• • 在遍历过程中，同时维护两个全局变量：

• • • 全局最小值：所有设备的最小值中最小的那个。

  • • 全局最小次小值：所有设备的次小值中最小的那个。

3. 调整临时总和：

• • 上面假设每台设备都移走了自己的最小值，但被移走的这些最小值必须集中放到某台设备中。如果所有设备都移走了自己的最小值，那么作为接收站的那台设备会收到其他设备的最小值，其中包含全局最小值。这个全局最小值很可能比接收站自己的次小值还要小，因此接收站最终的实际评分会被拉低到全局最小值。

• • 与其让所有设备都移走最小值再让接收站被拉低，不如选择一台设备作为接收站，让它不参与“移走最小值”的操作，或者让它最终评分为全局最小值。为了最大化总和，应该选择次小值最小的那台设备作为接收站，因为这样损失的次小值最小。

• • 具体做法是：从临时总和中减去全局最小次小值，再加上全局最小值。也就是把某台设备的次小值替换成全局最小值。这样得到的最终总和就是最大可能的总评分之和。

4. 举例验证：
输入 units = [[5,5,5],[1,1,1]]。

• • 第一台设备：最小值是 5，次小值也是 5。

• • 第二台设备：最小值是 1，次小值也是 1。

• • 临时总和 = 5 + 1 = 6。

• • 全局最小值 = min(5,1) = 1。

• • 全局最小次小值 = min(5,1) = 1。

• • 最终总和 = 6 + (1 - 1) = 6。
  所以输出 6。

5. 复杂度分析：

• • 时间复杂度：需要遍历整个二维数组一次，对每个单元进行常数次比较和更新。总单元数为 m * n，题目保证 m * n <= 200000。因此时间复杂度为 O(m * n)。

• • 额外空间复杂度：算法只使用了若干个变量来保存最小值、次小值、全局最小值和全局最小次小值等，没有使用与输入规模相关的额外数组或数据结构。因此额外空间复杂度为 O(1)。

package main

 import (
    "fmt"
    "math"
)

 func maxRatings(units [][]int) int64 {
    ans := 0
    if len(units[0]) == 1 {
        // 每个设备都只有一个单元
        for _, unit := range units {
            ans += unit[0]
        }
        return int64(ans)
    }

     mn, mn2 := math.MaxInt, math.MaxInt
    for _, unit := range units {
        // 计算最小次小
        unitMin, unitMin2 := math.MaxInt, math.MaxInt
        for _, x := range unit {
            if x < unitMin {
                unitMin2 = unitMin
                unitMin = x
            } else if x < unitMin2 {
                unitMin2 = x
            }
        }

         ans += unitMin2 // 先加上次小
        mn2 = min(mn2, unitMin2)
        mn = min(mn, unitMin)
    }

     // 把包含 mn2 的那个设备作为集中站，存放每个设备的最小值
    ans += mn - mn2 // 把 ans 中的 mn2 替换成 mn
    return int64(ans)
}

 func main() {
    units := [][]int{{5, 5, 5}, {1, 1, 1}}
    result := maxRatings(units)
    fmt.Println(result)
}

Python完整代码如下：

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

 from typing import List

 def maxRatings(units: List[List[int]]) -> int:
    ans = 0

     # 每个设备只有一个单元时，直接求和即可
    if len(units[0]) == 1:
        for unit in units:
            ans += unit[0]
        return ans

     # mn 记录所有设备最小值中的最小值
    # mn2 记录所有设备次小值中的最小值
    mn = float('inf')
    mn2 = float('inf')

     for unit in units:
        unit_min = float('inf')
        unit_min2 = float('inf')

         # 找出当前设备的最小值和次小值
        for x in unit:
            if x < unit_min:
                unit_min2 = unit_min
                unit_min = x
            elif x < unit_min2:
                unit_min2 = x

         ans += unit_min2
        mn2 = min(mn2, unit_min2)
        mn = min(mn, unit_min)

     # 把全局最小次小值替换成全局最小最小值
    ans += mn - mn2
    return ans

 if __name__ == "__main__":
    units = [[5, 5, 5], [1, 1, 1]]
    result = maxRatings(units)
    print(result)

C++完整代码如下：

  

  

    

  


 using namespace std;

 int64_t maxRatings(const vector 
 
 int 
 >>& units) { 
 
 
     long long ans =  
 0 
 ; 
 
 
 
 
      
 // 每个设备都只有一个单元 
 
 
      
 if 
  (units[ 
 0 
 ].size() ==  
 1 
 ) { 
 
 
          
 for 
  ( 
 const 
  auto& unit : units) { 
 
 
             ans += unit[ 
 0 
 ]; 
 
 
         } 
 
 
          
 return 
  ans; 
 
 
     } 
 
 
 
 
      
 int 
  mn = numeric_limits< 
 int 
 >::max(); 
 
 
      
 int 
  mn2 = numeric_limits< 
 int 
 >::max(); 
 
 
 
 
      
 for 
  ( 
 const 
  auto& unit : units) { 
 
 
          
 int 
  unitMin = numeric_limits< 
 int 
 >::max(); 
 
 
          
 int 
  unitMin2 = numeric_limits< 
 int 
 >::max(); 
 
 
 
 
          
 // 计算当前设备的最小值和次小值 
 
 
          
 for 
  ( 
 int 
  x : unit) { 
 
 
              
 if 
  (x < unitMin) { 
 
 
                 unitMin2 = unitMin; 
 
 
                 unitMin = x; 
 
 
             }  
 else 
   
 if 
  (x < unitMin2) { 
 
 
                 unitMin2 = x; 
 
 
             } 
 
 
         } 
 
 
 
 
         ans += unitMin2;  
 // 先加上次小值 
 
 
         mn2 = min(mn2, unitMin2); 
 
 
         mn = min(mn, unitMin); 
 
 
     } 
 
 
 
 
      
 // 把包含 mn2 的那个设备作为集中站，存放每个设备的最小值 
 
 
     ans += mn - mn2;  
 // 把 ans 中的 mn2 替换成 mn 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> units = {{ 
 5 
 ,  
 5 
 ,  
 5 
 }, { 
 1 
 ,  
 1 
 ,  
 1 
 }}; 
 
 
     int64_t result = maxRatings(units); 
 
 
     cout << result << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

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