LeetCode_每日一题今日份_410.分割数组的最大值

淩亂°似流年 2023-03-01 12:44 32阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]

bool check(int* nums, int numsSize, int m, int x) {
        
        long long sum = 0; //当前分割子数组的和
        int cnt = 1; //已经分割出的子数组的数量（包括当前子数组）
        for (int i = 0; i < numsSize; i++) {
        
            if (sum + nums[i] > x) {
        
                cnt++;
                sum = nums[i];
            } else {
        
                sum += nums[i];
            }
        }
        return cnt <= m;
    }
    
    int splitArray(int* nums, int numsSize, int m) {
        
        long long left = 0, right = 0;
        for (int i = 0; i < numsSize; i++) {
        
            right += nums[i];
            if (left < nums[i]) {
        
                left = nums[i];
            }
        }
        while (left < right) {
        
            long long mid = (left + right) >> 1;
            if (check(nums, numsSize, m, mid)) {
        
                right = mid;
            } else {
        
                left = mid + 1;
            }
        }
        return left;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20230208/14c175bdf737490fb9046fcb97ba4961.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20230208/639bb8776bb143959c04f5e6790c2fde.png