LeetCode 3219. 切蛋糕的最小总开销 II — Java 实现题目概述给定一个 m × n 的矩形蛋糕需要切成 1 × 1 的小块。horizontalCut[i] 表示沿水平线 i 切割的开销verticalCut[j] 表示沿垂直线 j 切割的开销。每次切割可以将任意非 1 × 1 的蛋糕块切开。求最小总开销。---解题思路贪心策略优先切开销大的关键观察一条切割线被切到的次数等于在该切割之前已经完成的垂直切割次数 1如果是水平切割或水平切割次数 1如果是垂直切割。因此开销大的切割线应该尽早切这样它乘上的段数更少。这等价于- 将 horizontalCut 和 verticalCut 按降序排列- 每次选择当前剩余开销最大的切割线- 水平切割的开销要乘以当前的垂直段数垂直切割的开销要乘以当前的水平段数---Java 代码实现javaimport java.util.Arrays;class Solution {public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {// 按降序排列优先处理开销大的切割线Arrays.sort(horizontalCut);Arrays.sort(verticalCut);long ans 0;int i m - 2, j n - 2; // 从最大开销开始int h 1, v 1; // h: 水平段数, v: 垂直段数while (i 0 || j 0) {if (j 0 || (i 0 horizontalCut[i] verticalCut[j])) {// 优先切水平线ans (long) horizontalCut[i--] * v; // 乘以当前垂直段数h; // 水平段数 1} else {// 优先切垂直线ans (long) verticalCut[j--] * h; // 乘以当前水平段数v; // 垂直段数 1}}return ans;}}---关键点说明要点 说明降序排序 Arrays.sort() 默认升序所以从数组末尾开始遍历i m-2, j n-2段数含义 h 表示当前水平方向上有多少段蛋糕块v 表示垂直方向上有多少段乘法逻辑 水平切割一次会影响所有垂直段所以乘以 v垂直切割同理乘以 hlong 类型 结果可能很大需要用 long 避免溢出---示例验证示例 1m 3, n 2, horizontalCut [1,3], verticalCut [5]- 排序后horizontalCut [1,3], verticalCut [5]- 初始h1, v1, i1, j0- 第1轮horizontalCut[1]3 verticalCut[0]5? 否 → 切垂直线 5ans 5*1 5v2, j-1- 第2轮j0 → 切水平线 3ans 3*2 6h2, i0- 第3轮切水平线 1ans 1*2 2h3, i-1- 总开销5 6 2 13 ✓示例 2m 2, n 2, horizontalCut [7], verticalCut [4]- 排序后horizontalCut [7], verticalCut [4]- 第1轮7 4 → 切水平线 7ans 7*1 7h2, i-1- 第2轮切垂直线 4ans 4*2 8v2, j-1- 总开销7 8 15 ✓---复杂度分析- 时间复杂度O(m \log m n \log n)主要来自排序- 空间复杂度O(1)仅使用常数额外空间该解法与 LeetCode 官方题解一致已通过所有测试用例。