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

题目描述

这是 LeetCode 上的 1465. 切割后面积最大的蛋糕 ，难度为 中等。

矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 hs 和 vs，其中：

  • hs[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离
  • vs[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离

请你按数组 hs 和 vs 中提供的水平和竖直位置切割后，请你找出面积最大的那份蛋糕，并返回其面积。

由于答案可能是一个很大的数字，因此需要将结果 对 $10^9 + 7$ 取余 后返回。

示例 1：

1
2
3
4
5
输入：h = 5, w = 4, hs = [1,2,4], vs = [1,3]

输出：4 

解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。

示例 2：

1
2
3
4
5
输入：h = 5, w = 4, hs = [3,1], vs = [1]

输出：6

解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色和黄色的两份蛋糕面积最大。

示例 3：

1
2
3
输入：h = 5, w = 4, hs = [3], vs = [3]

输出：9

提示：

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

贪心

由于求是“最大”蛋糕面积，水平/垂直方向的连续段必然由「同方向且相邻」的切割位置（或是蛋糕边界）所构成。

这点可通过反证法证明：如果最终蛋糕的（左右或上下）边缘不是由「相邻」的切割位置（或是蛋糕边界）决定，而是由跨越某些切割点的位置所决定的话，那么这个蛋糕必不是“完整”一块。

用题面的示例 $1$ 来举个 🌰，我们仅分析水平方向（hs = [1, 2, 4]）：

最终蛋糕的在该方向的连续段大小，只能是 [上边缘, 切割点 1]、[切割点 1, 切割点 2]、[切割点 2, 切割点 4] 和 [切割点 4, 下边缘] 四个之一，而不可能由非相邻切割点所组成，例如 [切割点 1, 切割点 4]（会被 切割点 2 所一分为二，不再完整）。

因此，我们可先对 hs 和 vs 进行排序，从而确保我们在遍历 hs 和 vs 过程中，处理到的均为「同反向且相邻」的切割位置。

随后，利用俩方向相互独立，分别求出俩方向连续段的最大长度，两者乘积即是答案。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    int MOD = (int)1e9+7;
    public int maxArea(int h, int w, int[] hs, int[] vs) {
        Arrays.sort(hs);
        Arrays.sort(vs);
        int n = hs.length, m = vs.length;
        int mh = Math.max(hs[0], h - hs[n - 1]), mv = Math.max(vs[0], w - vs[m - 1]);
        for (int i = 1; i < n; i++) mh = Math.max(mh, hs[i] - hs[i - 1]);
        for (int i = 1; i < m; i++) mv = Math.max(mv, vs[i] - vs[i - 1]);
        return (int)((mh * 1L * mv) % MOD);
    }
}

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxArea(int h, int w, vector<int>& hs, vector<int>& vs) {
        int MOD = 1e9+7;
        sort(hs.begin(), hs.end());
        sort(vs.begin(), vs.end());
        int n = hs.size(), m = vs.size();
        int mh = max(hs[0], h - hs[n - 1]), mv = max(vs[0], w - vs[m - 1]);
        for (int i = 1; i < n; i++) mh = max(mh, hs[i] - hs[i - 1]);
        for (int i = 1; i < m; i++) mv = max(mv, vs[i] - vs[i - 1]);
        return (mh * 1L * mv) % MOD;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxArea(self, h: int, w: int, hs: List[int], vs: List[int]) -> int:
        MOD = 10 ** 9 + 7
        hs.sort()
        vs.sort()
        n, m = len(hs), len(vs)
        mh, mv = max(hs[0], h - hs[n - 1]), max(vs[0], w - vs[m - 1])
        for i in range(1, n):
            mh = max(mh, hs[i] - hs[i - 1])
        for i in range(1, m):
            mv = max(mv, vs[i] - vs[i - 1])
        return (mh * mv) % MOD

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
function maxArea(h: number, w: number, hs: number[], vs: number[]): number {
    const MOD = BigInt(1e9 + 7);
    hs.sort((a,b)=>a-b);
    vs.sort((a,b)=>a-b);
    const n = hs.length, m = vs.length;
    let mh = Math.max(hs[0], h - hs[n - 1]), mv = Math.max(vs[0], w - vs[m - 1]);
    for (let i = 1; i < n; i++) mh = Math.max(mh, hs[i] - hs[i - 1]);
    for (let i = 1; i < m; i++) mv = Math.max(mv, vs[i] - vs[i - 1]);
    return Number((BigInt(mh) * BigInt(mv)) % MOD);
};

  • 时间复杂度：$O(m\log{m} + n\log{n})$
  • 空间复杂度：$O(\max(\log{m}, \log{n})$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1465 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。