LeetCode 410——分割数组的最大值

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1. 题目

2. 解答

此题目为今日头条 2018 AI Camp 5 月 26 日在线笔试编程题第二道——最小分割分数。



class Solution {

public:

    // 若分割数组的最大值为 value，判断能否进行划分

    bool cansplit(vector<int>& nums, int value, int m)

    {

        int len = nums.size();

        int i = 0;

        int sum = 0;

        int split_count = 0; // 分割次数

        // 依次往后求和，若和小于等于 value，则继续加；

        // 若和大于 value，则分割次数加 1，从当前位置开始将和清零，重新开始

        for (i = 0; i < len; i++)

        {

            if (sum + nums[i] <= value)

            {

                sum += nums[i];

            }

            else

            {

                split_count++;

                sum = nums[i];

            }

            if (split_count == m)  // 分割次数超出 m, 不满足划分

            {

                return false;

            }

        }

        return true;

    }

    int splitArray(vector<int>& nums, int m) {

        int len = nums.size();

        int i = 0;

        // 分割数组的最大值介于数组的最大元素和数组所有元素的和之间

        int max = nums[0];

        int sum = 0;

        for (i = 0; i < len; i++)

        {

            if (nums[i] > max)

            {

                max = nums[i];

            }

            sum += nums[i];

        }

        int left = max;

        int right = sum;

        int mid = 0;

        while(left < right)

        {

            mid = left + (right - left) / 2;

            if (cansplit(nums, mid, m)) // 能划分，继续找有没有更小的值

            {

                right = mid; //不减是因为无法确保减一之后的数是否满足划分

            }

            else // 不能划分，增大数值继续寻找

            {

                left = mid + 1;

            }

        }

        return left;

        // 最终 left = right 结束，left 值就是所求

    }

};