LeetCode 补充题 7. 木头切割问题

Categories:

题目描述
思路分析
1. 解法一：二分答案（推荐）
相似题目

题目描述

✅ 补充题 7. 木头切割问题

思路分析

解法一：二分答案（推荐）

核心思路：

单段长度越长，能切出的段数越少，具有单调性。

二分答案 len，判断是否能切出至少 k 段。

使用上取整的区间收缩，找到最大可行长度。

复杂度分析：

时间复杂度：O(n log M)，其中 n 表示木头数量，M 为最大长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int woodCut(int[] woods, int k) {
        int max = 0;
        for (int v : woods) {
            max = Math.max(max, v);
        }
        if (max == 0) {
            return 0;
        }

        int left = 1;
        int right = max;

        // 二分最大可行长度
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canCut(woods, k, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return right;
    }

    private boolean canCut(int[] woods, int k, int len) {
        long count = 0;
        for (int v : woods) {
            count += v / len;
        }
        return count >= k;
    }
}

func woodCut(woods []int, k int) int {
	maxLen := 0
	for _, v := range woods {
		if v > maxLen {
			maxLen = v
		}
	}
	if maxLen == 0 {
		return 0
	}

	left, right := 1, maxLen

	// 二分最大可行长度
	for left <= right {
		mid := left + (right-left)/2
		if canCut(woods, k, mid) {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return right
}

func canCut(woods []int, k int, length int) bool {
	count := 0
	for _, v := range woods {
		count += v / length
	}
	return count >= k
}

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分答案
1011. 在 D 天内送达包裹的能力	中等	二分答案
410. 分割数组的最大值	困难	二分答案
1482. 制作 m 束花所需的最少天数	中等	二分答案
2064. 分配给商店的最多商品的最小值	中等	二分答案

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/16524784