【每日一题】切割后面积最大的蛋糕

Tag

【排序】【数组】【2023-10-27】

---

题目来源

1465. 切割后面积最大的蛋糕

---

题目解读

切割后面积最大的蛋糕。

---

解题思路

方法一：排序

本题较为简单，找出最大的宽和高，然后返回乘积即可。为了找出找出最大的宽和高，我们需要计算相邻两条切痕之间的距离（包括边界与最近的切痕之间的距离）。为了便于计算，可以对水平方向和竖直方向的切痕进行排序。具体实现见下方代码。

实现代码

class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        const int MOD = 1e9 + 7;
        sort(verticalCuts.begin(), verticalCuts.end());
        sort(horizontalCuts.begin(), horizontalCuts.end());

        long long width = 0, heigh = 0, prev = 0;
        for (auto vert : verticalCuts) {
            width = max(width, vert - prev);
            prev = vert;
        }
        width = max(width, w - prev);

        prev = 0;
        for (auto hor : horizontalCuts) {
            heigh = max(heigh, hor - prev);
            prev = hor;
        }
        heigh = max(heigh, h - prev);

        long long res = (long long) width * heigh % MOD;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

复杂度分析

时间复杂度：$O(nlogn)$，$n$ 为数组 horizontalCuts 和 verticalCuts 的最大长度。

空间复杂度：$O(nlogn)$。

其他语言

python3

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        width, heigh, prev = 0, 0, 0
        mod = 10 ** 9 + 7
        horizontalCuts.sort()
        verticalCuts.sort()

        for vert in verticalCuts:
            width = max(width, vert - prev)
            prev = vert
        width = max(width, w - prev)

        prev = 0
        for hor in horizontalCuts:
            heigh = max(heigh, hor - prev)
            prev = hor
        heigh = max(heigh, h - prev)

        res = width * heigh % mod
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。