跳转至

410 分割数组的最大值

思路

class Solution {
public:
    int f(vector<int>& nums, int x){
        int cnt = 0;
        int i = 0;
        while(i < nums.size()){
            int sum = x;
            while(i < nums.size()){
                if(sum >= nums[i]){
                    sum -= nums[i];
                    i++;
                }else{
                    break;
                }
            }
            cnt++;
        }
        return cnt;
    }
    int splitArray(vector<int>& nums, int k) {
        int left = 0, right = 0;
        for(int num : nums){
            left = max(left, num);
            right += num;
        }
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(f(nums, mid) == k){
                right = mid - 1;
            }else if(f(nums, mid) < k){
                right = mid - 1;
            }else if(f(nums, mid) > k){
                left = mid + 1;
            }
        }
        return left;
    }
};