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

链接：1465.切割后面积最大的蛋糕
难度：Medium
标签：贪心、数组、排序
简介：请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。

题解 1 - cpp

• 编辑时间：2023-10-27
• 执行用时：64ms
• 内存消耗：31.09MB
• 编程语言：cpp
• 解法介绍：排序后计算间隔。

class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        long long resH = 0, resW = 0;
        sort(horizontalCuts.begin(), horizontalCuts.end());
        horizontalCuts.insert(horizontalCuts.begin(), 0);
        horizontalCuts.push_back(h);
        for (int i = 1; i < horizontalCuts.size(); i++) resH = max(resH, (long long)horizontalCuts[i] - horizontalCuts[i - 1]);
        sort(verticalCuts.begin(), verticalCuts.end());
        verticalCuts.insert(verticalCuts.begin(), 0);
        verticalCuts.push_back(w);
        for (int i = 1; i < verticalCuts.size(); i++) resW = max(resW, (long long)verticalCuts[i] - verticalCuts[i - 1]);
        return resH * resW % ((long long)1e9 + 7);
    }
};

题解 2 - python

• 编辑时间：2023-10-27
• 执行用时：108ms
• 内存消耗：27.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        res = [0, 0]
        horizontalCuts.sort()
        horizontalCuts = [0] + horizontalCuts + [h]
        for i in range(1, len(horizontalCuts)):
            res[0] = max(res[0], horizontalCuts[i] - horizontalCuts[i - 1])
        
        verticalCuts.sort()
        verticalCuts = [0] + verticalCuts + [w]
        for i in range(1, len(verticalCuts)):
            res[1] = max(res[1], verticalCuts[i] - verticalCuts[i - 1])
        return res[0] * res[1] % (10 ** 9 + 7)

题解 3 - rust

• 编辑时间：2023-10-27
• 执行用时：16ms
• 内存消耗：4.29MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn max_area(h: i32, w: i32, horizontal_cuts: Vec<i32>, vertical_cuts: Vec<i32>) -> i32 {
        let mut horizontal_cuts = horizontal_cuts
            .into_iter()
            .map(|v| v as i64)
            .collect::<Vec<_>>();
        horizontal_cuts.sort();
        horizontal_cuts.insert(0, 0);
        horizontal_cuts.push(h as i64);
        let mut h = 0;
        for i in 1..horizontal_cuts.len() {
            h = h.max(horizontal_cuts[i] - horizontal_cuts[i - 1]);
        }
        let mut vertical_cuts = vertical_cuts
            .into_iter()
            .map(|v| v as i64)
            .collect::<Vec<_>>();
        vertical_cuts.sort();
        vertical_cuts.insert(0, 0);
        vertical_cuts.push(w as i64);
        let mut w = 0;
        for i in 1..vertical_cuts.len() {
            w = w.max(vertical_cuts[i] - vertical_cuts[i - 1]);
        }
        (h * w % (10i64.pow(9) + 7)) as i32
    }
}