526互联

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

发布时间 2023-10-27 12:11:59作者: DawnTraveler

1.题目介绍

矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：
\(\text{horizontalcuts [i] 是从矩形蛋糕顶部到第 i 个水平切口的距离}\)
\(\text{verticalCuts [j] 是从赶形蛋糕的左侧到第 j 个贤盲切口的距离}\)
请你按数组 horizontalCuts 和 verticalCuts中提供的水平和竖直位置切割后，请你找出 面积面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 \(10^9 + 7\) 取余 后返回。

image

image

image

2.题解（贪心算法）

问题转化

这里最重要的是要理解示例图，在我们将0和边界值也加入两数组后，构成的横/竖n条遍都可以通过平移与另一条竖/横构成一个矩形！！！所以问题也就转变成了分别求两个数组中间距最大的两个元素，然后我们就可以通过平移构成图中所有可能的切割区域。

就举个例子，这里的横（0->1 = 1， 1->3 = 2 3->4 = 1）,竖(0->1 = 1, 1->2 = 1, 2->4 = 2, 4->5 = 1),分别取这里面长度最大的两个，也就是1->3（向下平移）,2->4（向右平移）直到两者相较于一点，然后补充为矩形即可。
image

代码

1.我的代码

总体思路就是先将数组排序，然后将0和边界值分别加入两个数组，之后分别遍历数组找出间隔最大的一组计算出面积。

这里注意一个东西，题目说：由于答案可能是一个很大的数字，因此需要将结果 对 \(10^9 + 7\) 取余 后返回。这里我们就要考虑溢出的情况，我们会发现使用 return (res_w * res_h % 1000000007);依旧会导致double类型无法转化int的问题，使用 return (int)(res_w * res_h % 1000000007);依旧会导致溢出的问题，使用return (long long)(res_w * res_h % 1000000007);也会有溢出的问题？

这是为什么呢？这是因为（由运算符的优先级和结合性（左结合））先进行res_w * res_h 的乘法运算时是将其看做int类型进行运算的，得到的结果过大无法存储于int中导致溢出，也就算不到后面一步的求余运算和以及后面的类型转换了。

这里我们就可以这样写：return (int)((long long)res_w * res_h % 1000000007);这里现将res_w转化为long long类型，这样乘法运算就不会溢出，这里的int虽然可以省略（系统会隐式转换），但是为了表达清晰，这里特意标出。（注意：从较大类型（long long）转换为较小类型（int），有可能会发生数据截断，一般不推荐这么做）

//
// Created by trmbh on 2023-10-27.
//
#include<vector>
#include <algorithm>
#include <cmath>
#include <iostream>
class Solution {
public:
    int maxArea(int h, int w, std::vector<int>& horizontalCuts, std::vector<int>& verticalCuts) {
        sort(horizontalCuts.begin(),horizontalCuts.end());
        sort(verticalCuts.begin(),verticalCuts.end());
        horizontalCuts.insert(horizontalCuts.begin(), 0);
        horizontalCuts.push_back(h);
        verticalCuts.insert(verticalCuts.begin(),0);
        verticalCuts.push_back(w);
        int res_h= 0, res_w = 0;
        for (int i = 1; i < horizontalCuts.size(); i++){
            res_h = std::max(res_h, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        for (int i = 1; i < verticalCuts.size(); i++){
            res_w = std::max(res_w, verticalCuts[i] - verticalCuts[i-1]);
        }
        return (int)(res_w * res_h % 1000000007);
    }
};

int main(){
    Solution solution;
    std::vector<int> arr_h = {5,2,6,3}, arr_v = {1, 4};
    std::cout << solution.maxArea(8,5,arr_h,arr_v) << std::endl;
}

2.力扣题解

这里使用了lambda表达式（求最大矩形长和宽的方式基本相同，用lambda表达式可简化代码），名为 calMax。这个 lambda 函数接受两个参数：一个整数向量的引用 (arr) 和一个整数 (boardr)，然后返回一个整数。

他这里没有直接在数组里面加上0和边界值（尤其上首项加0，确实太浪费时间，所有后面的项都要向后推），而是将其单独拉出来，为了方便实用强化的for语句，加入了一个pre存储前一个元素；在最后的时候，再将边界值-pre和res比较，就将所有边均计算在内了。

class Solution {
public:
    int maxArea(int h, int w, std::vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        int mod = 1e9 + 7;
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        auto calMax = [](std::vector<int> &arr, int boardr) -> int {
            int res = 0, pre = 0;
            for (int i : arr) {
                res = std::max(i - pre, res);
                pre = i;
            }
            return std::max(res, boardr - pre);
        };
        return (long long)calMax(horizontalCuts, h) * calMax(verticalCuts, w) % mod;
    }
};