LeetCode 补充题 7. 木头切割问题
题目描述
给定整数数组
woods和正整数k，其中woods[i]表示第i根木头的长度。你可以切割这些木头，得到至少
k段长度相同的小木段。小木段的长度必须为正整数，每一段都必须来自某一根原木；剩余部分可以丢弃，不能把不同木头拼接起来。请返回小木段可以采用的最大长度。
示例 1：
输入：woods = [4,7,2,10,5], k = 5
输出：4
解释：各根木头分别能切出 1、1、0、2、1 段长度为 4 的木段，共 5 段。
提示：
- 保证存在正整数长度的可行切法，即答案至少为
1。 - 切出的段数超过
k也满足要求。
题意分析
有若干根木头，要从中切出至少
k段等长的小木段，求能采用的最大正整数段长。k为正数，每段必须来自同一根原木，剩余零头可以丢弃，但不能跨木头拼接。切出超过
k段也满足要求，只需留下其中需要的部分。原题保证有解；代码还额外兼容无解输入：如果连长度为一都凑不出足够段数，就返回零。空数组或全部为零的木头也按这一扩展规则处理。
解法：二分答案找最大可行长度
核心思路
[!blue]
先固定候选段长
length。长度为wood的一根木头最多切出wood / length段，使用整数除法向下取整。分别计算每根的段数并求和，达到k就说明该长度可行。段长增加时，每根能切出的段数只会减少或不变，所以可行长度形成从小到大的一段前缀。目标是这一段中最大的值，可以二分长度范围，无需反复尝试所有整数。
正长度下界是一，上界是最长原木，任何小段都不可能比来源木头更长。代码用
ans保存已经验证过的最大可行长度，闭区间[left, right]则只表示尚未处理的候选，二者含义不同。若中点可行，先把它记录到
ans，再向右寻找更长长度；若不可行，更长的也都不可行，令右界降到中点前一位。区间为空时，所有可能改善答案的长度都已处理，返回记录值。完全无解时，ans保持零。判定累计到足够段数即可结束，后续原木不会让数量变少。最后一个候选已经可行时直接返回，避免在最大整数长度处执行加一；Go 还在累加前比较尚缺段数，防止机器整数上界附近的段数相加溢出。
解题步骤
- 扫描木头得到最长长度，初始化
left = 1、ans = 0。- 在闭区间非空时取中点，逐根计算能切出的整数段数。
- 达到
k判为可行，保存中点，并继续检查更大的候选；已是最后一个候选则直接返回。- 段数不足时，排除中点及更长长度。
- 搜索结束返回
ans。
代码实现
class Solution {
public int woodCut(int[] woods, int k) {
int right = 0;
for (int wood : woods) {
right = Math.max(right, wood);
}
int left = 1;
int ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canCut(woods, k, mid)) {
// 记录已验证的可行长度，后续区间只处理尚未确定的候选
ans = mid;
// 最后一个候选已确认可行，直接结束，避免上界处继续加一
if (mid == right) {
return ans;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
private boolean canCut(int[] woods, int k, int len) {
long count = 0;
for (int wood : woods) {
// 每根木头分别整除，不能跨木头拼接零头
count += wood / len;
if (count >= k) {
return true;
}
}
return false;
}
}
func woodCut(woods []int, k int) int {
right := 0
for _, wood := range woods {
if wood > right {
right = wood
}
}
left, ans := 1, 0
for left <= right {
mid := left + (right-left)/2
if canCutWood(woods, k, mid) {
// 记录已验证的可行长度，后续区间只处理尚未确定的候选
ans = mid
// 最后一个候选已确认可行，直接结束，避免上界处继续加一
if mid == right {
return ans
}
left = mid + 1
} else {
right = mid - 1
}
}
return ans
}
func canCutWood(woods []int, k, length int) bool {
var count int64
for _, wood := range woods {
// 每根分别整除，先对比尚缺段数，避免累计相加溢出
pieces := int64(wood / length)
if pieces >= int64(k)-count {
return true
}
count += pieces
}
return false
}
复杂度分析
- 时间复杂度：$O(n\log(M+1))$，其中 $n$ 是原木数量，$M$ 是最长长度。初始扫描为线性，每次二分判定至多检查全部原木。
- 空间复杂度：$O(1)$，只保存搜索边界、已知答案和段数。
关键点总结
[!green]
- 按根向下取整，才能体现零头无法拼接的限制。
- 总段数随候选长度单调不增，查找的是最后一个可行长度。
- 中点记录后移出候选区间，因此循环结束返回
ans，而不是直接返回某个搜索边界。- 只要求段数足够，判定无需精确算完所有可切段数。
易错点总结
[!yellow]
- 下界取零会产生除零，零只作为无解返回值，不参与判定。
- 将所有原木总长相加后再除，会错误地拼接各根零头。
- 必须判断段数大于或等于
k，不能拒绝恰好够用的长度。- 可行中点要继续向右查找，否则只能得到某个可行长度，不能保证最大。
- 搜索结束时左端通常已越过最后可行值，不能把它当作答案返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1891. 割绳子 | 中等 | 同样把每根材料独立切成等长正整数段，要求总段数足够，并最大化可行段长。 |
| 875. 爱吃香蕉的珂珂 | 中等 | 都可二分答案，但本题段数用向下取整且随段长增大而减少，吃香蕉用向上取整计算时间。 |