1183：矩阵中 1 的最大数量（★★★）

力扣第 8 场双周赛第 4 题

题目

现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。

而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。

请你设计一个算法，计算矩阵中最多可以有多少个 1。

示例 1：

输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
输出：4
解释：
题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。
最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：
[1,0,1]
[0,0,0]
[1,0,1]

示例 2：

输入：width = 3, height = 3, sideLength = 2, maxOnes = 2
输出：6
解释：
[1,0,1]
[1,0,1]
[1,0,1]

提示：

• 1 <= width, height <= 100
• 1 <= sideLength <= width, height
• 0 <= maxOnes <= sideLength * sideLength

分析

将矩阵从左到右，从上到下划分为不相交的正方形子阵（最边上可能不完整）。先放的位置应该是尽可能多的分块都有的位置。

解答

1
2
3
4
5
6
7
8
9

class Solution:
    def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:
        n = sideLength
        res = []
        for i,j in product(range(n),range(n)):
            x = (width-i-1)//n+1
            y = (height-j-1)//n+1
            res.append(x*y)
        return sum(nlargest(maxOnes,res))

56 ms