Keshawn_lu's Blog

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

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

题目简介：

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

请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果对 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 中的所有元素各不相同

思路：

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

为此，我们将两个数组分别填入0和w, 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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网