[LeetCode] 每日一题 3219. 切蛋糕的最小总开销 II

题目链接

题目描述

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

• horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。

• verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。

2. 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例输入

示例 1

输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]

输出：13

解释：
沿着垂直线 0 切开蛋糕，开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]

输出：15

解释：
沿着水平线 0 切开蛋糕，开销为 7 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
总开销为 7 + 4 + 4 = 15 。

提示

• 1 <= m, n <= 105

• horizontalCut.length == m - 1

• verticalCut.length == n - 1

• 1 <= horizontalCut[i], verticalCut[i] <= 10^3

题解

解题思路

本题和前几天的 3218. 切蛋糕的最小总开销 I 解法思路完全一致

1. 逆向合并：可以将问题看作一个“反向操作”，即从 1×1 的小块开始，不断将矩形区域合并成最终的 m × n 蛋糕。每次选择开销最小的合并方式。

2. 最小生成树的思想：这种问题类似于构建最小生成树，我们可以借鉴 Kruskal 算法的贪心策略，始终优先选择当前开销最小的切割方向。

3. 贪心策略：

   • 优先选择较小的切割开销。

   • 若选择水平切割，则会对所有列有效；若选择垂直切割，则会对所有行有效。

算法步骤

1. 对 horizontalCut 和 verticalCut 分别排序，确保优先考虑小的切割开销。

2. 使用两个指针 indexH 和 indexV 遍历两个数组，按照贪心策略合并矩形区域。

3. 更新结果 ans：

   • 如果当前选择水平切割，更新 ans+=当前水平开销 × 剩余列数。

   • 如果选择垂直切割，更新 ans+=当前垂直开销 × 剩余行数。

代码实现

class Solution {
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        long ans = 0;
        int indexH = 0, indexV = 0;
        while (indexH < m - 1 || indexV < n - 1) {
            if (indexV == n - 1 || indexH < m - 1 && horizontalCut[indexH] < verticalCut[indexV]) {
                // 上下连边
                ans += horizontalCut[indexH++] * (n - indexV);
            } else {
                // 左右连边
                ans += verticalCut[indexV++] * (m - indexH);
            }
        }
        return ans;
    }
}

复杂度分析

1. 时间复杂度：

   • 对 horizontalCut 和 verticalCut 排序的复杂度为 O(mlogm + nlogn)。

   • 遍历两个数组的复杂度为 O(m+n)。

   • 总复杂度为 O(mlogm + nlogn)。

2. 空间复杂度：

   • 排序操作为原地排序，不需要额外空间。

   • 总空间复杂度为 O(1)。

总结

这道题采用了逆向思维，将切割问题转化为合并问题，并结合 Kruskal 算法的贪心策略，保证了切割总开销最小。

这种思路不仅简化了问题，还体现了对算法思想的灵活运用：通过转换思维方向，化繁为简.

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。