LeetCode题解(1465)：切割后面积最大的蛋糕(Python)

103 阅读 0 评论 68 点赞

我是靠谱客的博主纯情篮球，这篇文章主要介绍LeetCode题解(1465)：切割后面积最大的蛋糕(Python)，现在分享给大家，希望可以做个参考。

题目：原题链接（中等）

标签：数组

解法	时间复杂度	空间复杂度	执行用时
Ans 1 (Python)	$O (H l o g H + V l o g V)$	$O (l o g H + l o g V)$	120ms (77.67%)
Ans 2 (Python)
Ans 3 (Python)

解法一：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    _MOD = 10 ** 9 + 7

    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        width, height = 0, 0

        horizontalCuts.sort()
        horizontalCuts.append(h)
        last = 0
        for n in horizontalCuts:
            height = max(height, n - last)
            last = n

        verticalCuts.sort()
        verticalCuts.append(w)
        last = 0
        for n in verticalCuts:
            width = max(width, n - last)
            last = n

        return width * height % self._MOD