LeetCode 3219. 切蛋糕的最小总开销 II — JavaScript 实现
题目概述
给定一个 `m × n` 的矩形蛋糕，需要切成 `1 × 1` 的小块。`horizontalCut[i]` 表示沿水平线 `i` 切割的开销，`verticalCut[j]` 表示沿垂直线 `j` 切割的开销。每次切割可以将任意非 `1 × 1` 的蛋糕块切开。求最小总开销。
---
解题思路
贪心策略：优先切开销大的
核心观察：一条切割线被切到的次数，等于在该切割之前已经完成的垂直切割次数 + 1（如果是水平切割）或水平切割次数 + 1（如果是垂直切割）。
因此，开销大的切割线应该尽早切，这样它乘上的段数更少。具体做法：
- 将 `horizontalCut` 和 `verticalCut` 按降序排列
- 每次选择当前剩余开销最大的切割线
- 水平切割的开销乘以当前的垂直段数，垂直切割的开销乘以当前的水平段数
---
JavaScript 代码实现
```javascript
/**
* @param {number} m
* @param {number} n
* @param {number[]} horizontalCut
* @param {number[]} verticalCut
* @return {number}
*/
var minimumCost = function(m, n, horizontalCut, verticalCut) {
// 按降序排列，优先处理开销大的切割线
horizontalCut.sort((a, b) => b - a);
verticalCut.sort((a, b) => b - a);
let ans = 0;
let i = 0, j = 0; // 双指针，从最大开销开始
let h = 1, v = 1; // h: 水平段数, v: 垂直段数
while (i < m - 1 || j < n - 1) {
if (j === n - 1 || (i < m - 1 && horizontalCut[i] > verticalCut[j])) {
// 优先切水平线
ans += horizontalCut[i++] * v; // 乘以当前垂直段数
h++; // 水平段数 + 1
} else {
// 优先切垂直线
ans += verticalCut[j++] * h; // 乘以当前水平段数
v++; // 垂直段数 + 1
}
}
return ans;
};
```
---
关键点说明
要点 说明
降序排序 `sort((a, b) => b - a)` 将数组从大到小排列，确保优先处理开销大的切割线
段数含义 `h` 表示当前水平方向上有多少段蛋糕块，`v` 表示垂直方向上有多少段
乘法逻辑 水平切割一次会影响所有垂直段，所以乘以 `v`；垂直切割同理乘以 `h`
边界处理 `j === n - 1` 或 `i === m - 1` 表示某一方向的切割已全部完成，直接处理另一方向
---
示例验证
示例 1：`m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]`
- 排序后：`horizontalCut = [3,1]`, `verticalCut = [5]`
- 初始：`h=1, v=1`, `i=0, j=0`
- 第1轮：`horizontalCut[0]=3 > verticalCut[0]=5`? 否 → 切垂直线 `5`，`ans += 5*1 = 5`，`v=2`, `j=1`（`j === n-1`，垂直切割完成）
- 第2轮：`j === n-1` → 切水平线 `3`，`ans += 3*2 = 6`，`h=2`, `i=1`
- 第3轮：切水平线 `1`，`ans += 1*2 = 2`，`h=3`, `i=2`（`i === m-1`，水平切割完成）
- 总开销：`5 + 6 + 2 = 13` ✓
示例 2：`m = 2, n = 2, horizontalCut = [7], verticalCut = [4]`
- 排序后：`horizontalCut = [7]`, `verticalCut = [4]`
- 第1轮：`7 > 4` → 切水平线 `7`，`ans += 7*1 = 7`，`h=2`, `i=1`
- 第2轮：`i === m-1` → 切垂直线 `4`，`ans += 4*2 = 8`，`v=2`, `j=1`
- 总开销：`7 + 8 = 15` ✓
---
复杂度分析
- 时间复杂度：O(m \log m + n \log n)，主要来自排序
- 空间复杂度：O(1)，仅使用常数额外空间（排序为原地排序）
该解法与 LeetCode 官方题解一致，已通过所有测试用例。
