Keshawn_lu's Blog

Leetcode 5425. 切割后面积最大的蛋糕

字数统计: 581阅读时长: 2 min
2020/05/31 Share

题目简介:

矩形蛋糕的高度为 h 且宽度为 w,给你两个整数数组 horizontalCutsverticalCuts,其中 horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离,类似地, verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。

请你按数组 horizontalCutsverticalCuts 中提供的水平和竖直位置切割后,请你找出 面积最大 的那份蛋糕,并返回其 面积 。由于答案可能是一个很大的数字,因此需要将结果对 10^9 + 7 取余后返回。

示例 1:

1
2
3
输入:h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
输出:4
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色的那份蛋糕面积最大。

示例 2:

1
2
3
输入:h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
输出:6
解释:上图所示的矩阵蛋糕中,红色线表示水平和竖直方向上的切口。切割蛋糕后,绿色和黄色的两份蛋糕面积最大。

示例 3:

1
2
输入:h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
输出:9

提示:

  • 2 <= h, w <= 10^9
  • 1 <= horizontalCuts.length < min(h, 10^5)
  • 1 <= verticalCuts.length < min(w, 10^5)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • 题目数据保证 horizontalCuts 中的所有元素各不相同
  • 题目数据保证 verticalCuts 中的所有元素各不相同

思路:

想法就是用贪心,将数组排序完后,将相邻差距最大的相乘即可。需要注意的就是数组只有一个值的情况,以及考虑左右边界的情况。

为此,我们将两个数组分别填入0w, h即可。

tip:

  • 需要用long long 来存储,用int会溢出

代码如下:

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
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {

long long max_x = 0;
long long max_y = 0;

horizontalCuts.push_back(0);
horizontalCuts.push_back(h);

verticalCuts.push_back(0);
verticalCuts.push_back(w);

sort(horizontalCuts.begin(), horizontalCuts.end());
sort(verticalCuts.begin(), verticalCuts.end());


for(int i = 1; i < horizontalCuts.size(); i++){

if(abs(horizontalCuts[i] - horizontalCuts[i - 1]) > max_y)
max_y = abs(horizontalCuts[i] - horizontalCuts[i - 1]);
}

for(int j = 1; j < verticalCuts.size(); j++){

if(abs(verticalCuts[j] - verticalCuts[j - 1]) > max_x)
max_x = abs(verticalCuts[j] - verticalCuts[j - 1]);
}

long long res = (max_x * max_y) % ((long long)pow(10, 9) + 7);

return res;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: