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;}
};

复杂度分析

时间复杂度：$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, 0mod = 10 ** 9 + 7horizontalCuts.sort()verticalCuts.sort()for vert in verticalCuts:width = max(width, vert - prev)prev = vertwidth = max(width, w - prev)prev = 0for hor in horizontalCuts:heigh = max(heigh, hor - prev)prev = horheigh = max(heigh, h - prev)res = width * heigh % modreturn res

写在最后

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

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

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