『LeetCode』2679 矩阵中的和

题目

给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：

矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的分数中。

请你返回最后的分数。

示例 1：

输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
输出：15
解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。

示例 2：

输入：nums = [[1]]
输出：1
解释：我们删除 1 并将分数增加 1 ，所以返回 1 。

提示：

1 <= nums.length <= 300
1 <= nums[i].length <= 500
0 <= nums[i][j] <= 10^{3}

题解

【矩阵中的和】优先队列

优先队列

题目不难理解，每次从矩阵的每一行中选取最大的数，然后再从这些数中选取最大的数，加到分数中，直到矩阵为空。

所以，关键是如何快速从每一行中找到最大的数，不难想到用优先队列是最简单的。

# Code language: Python
class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        nums = [[-a for a in row] for row in nums]
        for row in nums:
            heapq.heapify(row)
        return sum(max(-heapq.heappop(row) for row in nums) for _ in range(len(nums[0])))

// Code language: Java
class Solution {
    public int matrixSum(int[][] nums) {
        int n = nums.length, m = nums[0].length, ans = 0;
        PriorityQueue<Integer>[] st = new PriorityQueue[n];
        for (int i = 0; i < n; ++i) {
            st[i] = new PriorityQueue<Integer>((a, b) -> b - a);
            for (int j = 0; j < m; ++j) st[i].add(nums[i][j]);
        }
        for (int i = 0; i < m; ++i) {
            int cur = 0;
            for (int j = 0; j < n; ++j) {
                cur = Math.max(cur, st[j].poll());
            }
            ans += cur;
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        int n = nums.size(), m = nums[0].size(), ans = 0;
        vector<priority_queue<int>> st(n, priority_queue<int>());
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) st[i].emplace(nums[i][j]);
        }
        for (int i = 0; i < m; ++i) {
            int cur = 0;
            for (int j = 0; j < n; ++j) {
                cur = max(cur, st[j].top());
                st[j].pop();
            }
            ans += cur;
        }
        return ans;
    }
};

时间复杂度: \(O(nm \log m)\), 建堆每行需要 \(O(m)\), 共 \(n\) 行，合计 \(O(nm)\), 每次从堆中取出最大值需要 \(O(\log m)\), 共 \(n\) 次，合计 \(O(n\log m)\)
空间复杂度: \(O(nm)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』2679 矩阵中的和

题目

标签

题解

优先队列