[Leetcode解題] 2679. Sum in a Matrix

13 November 2026
medium array sorting matrix simulation

題目

2679. Sum in a Matrix

給定一個整數矩陣 nums,初始分數為 0。重複以下操作,直到矩陣為空:

  1. 從每一列(row)各取出並移除一個最大值;若最大值重複,任選一個即可。
  2. 找出這一輪移除的所有數字中的最大值,加到分數中。

回傳最後的總分。

例如 nums = [[7, 2, 1], [6, 4, 2], [6, 5, 3], [3, 2, 1]]:三輪分別加上 7、5、3,所以答案是 15。

題目限制:列數介於 1 到 300,欄數介於 1 到 500,且 0 <= nums[i][j] <= 1000。

解題思路

1. 直接模擬會重複尋找最大值

假設矩陣有 m 列、n 欄。如果每一輪都掃描每列剩餘的元素,找出並刪除最大值,總共需要 n 輪。

單列的掃描次數為 n + (n - 1) + ... + 1,因此整體需要 $O(mn^2)$ 的時間。若使用陣列刪除元素,還可能需要搬移後面的元素。

觀察一列的取出順序:不論原本如何排列,總是先取最大值,再取第二大值,直到取完。這個順序可以透過排序一次取得。

2. 每列排序後,同一欄就是同一輪取出的數字

將每一列各自按照遞增順序排序:

原始矩陣              每列排序後
[7, 2, 1]             [1, 2, 7]
[6, 4, 2]      →      [2, 4, 6]
[6, 5, 3]             [3, 5, 6]
[3, 2, 1]             [1, 2, 3]

此時:

  • 最右欄是每列的最大值,對應第一輪。
  • 倒數第二欄是每列的第二大值,對應第二輪。
  • 最左欄是每列的最小值,對應最後一輪。

所以每一輪的得分,就是對應欄的最大值。我們不需要真的刪除元素,只需要掃描每一欄。

3. 為什麼程式可以從左往右累加?

題目實際上從最大值開始移除,對應排序後由右往左處理。但每一輪取出的數字已由排序結果決定,不會因為累加順序而改變。

最後只要求總和,而加法的順序不影響答案,因此程式可以直接由左往右,累加每一欄的最大值。

令排序後的矩陣為 a,答案可以寫成:

\[\text{score} = \sum_{j=0}^{n-1} \max_{0 \le i < m} a[i][j]\]

注意:必須先將每一列分別排序,才能讓同一欄的元素對應到同一輪。原始矩陣的欄位置並沒有這個意義。

範例推演

使用上面的矩陣,排序後依照題目操作順序,由右往左查看:

輪次 對應欄索引 每列移除的數字 本輪得分 累計分數
1 2 [7, 6, 6, 3] 7 7
2 1 [2, 4, 5, 2] 5 12
3 0 [1, 2, 3, 1] 3 15

若程式由左往右走訪,則依序加上 3 + 5 + 7,結果同樣是 15。

演算法步驟

  1. 將 nums 的每一列各自按照遞增順序排序。
  2. 初始化總分 score = 0。
  3. 走訪每一欄 j,找出所有列在該欄的最大值。
  4. 將這個最大值加到 score。
  5. 回傳 score。

C++ 實作

class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        int m = nums.size();
        int n = nums[0].size();

        for (auto& row : nums) {
            sort(row.begin(), row.end());
        }

        int score = 0;
        for (int j = 0; j < n; ++j) {
            int columnMax = 0;
            for (int i = 0; i < m; ++i) {
                columnMax = max(columnMax, nums[i][j]);
            }
            score += columnMax;
        }

        return score;
    }
};

auto& row 使用參考,才能直接排序矩陣中的每一列。由於所有元素都非負,columnMax 可以初始化為 0。

Python 實作

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        m, n = len(nums), len(nums[0])

        for row in nums:
            row.sort()

        score = 0
        for j in range(n):
            column_max = max(nums[i][j] for i in range(m))
            score += column_max

        return score

兩份實作都會直接修改輸入矩陣中各列的順序。

正確性說明

將每列遞增排序後,以 a[i][j] 表示第 i 列、第 j 欄的值。

第一輪移除每列的最大值,也就是 a[i][n - 1]。移除後,下一輪的最大值就是 a[i][n - 2]。依此類推,第 k 輪(從 1 開始)會從每列移除 a[i][n - k]。即使有重複值,排序後的取出順序仍然符合題意。

因此,第 k 輪的得分恰好是排序後第 n - k 欄的最大值。經過 n 輪,每一欄都恰好貢獻一次最大值。

演算法累加了所有欄的最大值,與題目每一輪得分的總和相同,因此會回傳正確答案。

複雜度分析

令 m 為列數、n 為每列的元素數量。

  • 時間複雜度:排序所有列需要 $O(mn \log n)$,掃描所有欄需要 $O(mn)$,合計為 $O(mn \log n + mn)$。當 n >= 2 時,可簡寫為 $O(mn \log n)$。
  • 額外空間複雜度:掃描與累加只需 $O(1)$;若計入排序的輔助空間,C++ 的 std::sort 一般使用 $O(\log n)$ 的堆疊空間,Python 的 list.sort() 最壞需要 $O(n)$ 的輔助空間。各列依序排序,因此不需要將這些空間再乘上 m。

常見錯誤

  • 直接對原矩陣逐欄取最大值:每列的最大值可能位於不同欄,必須先將每列排序,讓相同排名的元素對齊。
  • 將每列最大值直接加總:每一輪只加上所有移除值中的一個最大值,而不是加上這一輪移除的全部數字。
  • 把整個矩陣攤平後排序:題目要求每輪從每列各取一個值,必須保留元素所屬的列。
  • 每一列使用不同排序方向:所有列必須使用相同方向,才能讓同一欄對應到同一輪。
  • 忘記重設欄最大值:每處理新的一欄,都要重新初始化 columnMax,避免混入上一欄的結果。

相關文章