LeetCode 1231. 分享巧克力

Categories:

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

题目描述

✅ 1231. 分享巧克力

思路分析

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

核心思路：

设能分成 k+1 份，每份最小甜度为 x。

使用贪心从左到右切分，累计甜度达到 x 就切一段。

二分 x 的最大值。

复杂度分析：

时间复杂度：O(n log S)，其中 n 表示数组长度，S 表示甜度总和。

空间复杂度：O(1)。

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int left = 1;
        int right = 0;
        for (int s : sweetness) {
            right += s;
        }
        right /= (k + 1);

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (canSplit(sweetness, k + 1, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean canSplit(int[] sweetness, int pieces, int minSweet) {
        int count = 0;
        int sum = 0;

        for (int s : sweetness) {
            sum += s;
            if (sum >= minSweet) {
                count++;
                sum = 0;
            }
        }

        return count >= pieces;
    }
}

func maximizeSweetness(sweetness []int, k int) int {
	left := 1
	right := 0
	for _, s := range sweetness {
		right += s
	}
	right /= (k + 1)

	for left < right {
		mid := left + (right-left+1)/2
		if canSplit(sweetness, k+1, mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

func canSplit(sweetness []int, pieces int, minSweet int) bool {
	count := 0
	sum := 0
	for _, s := range sweetness {
		sum += s
		if sum >= minSweet {
			count++
			sum = 0
		}
	}
	return count >= pieces
}

相似题目

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/48400132