LC 410. 分割数组的最大值

发布时间:2024年01月21日

410. 分割数组的最大值

难度: 困难

题目大意:

给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小。

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= min(50, nums.length)

示例 1:

输入:nums = [7,2,5,10,8], k = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

分析

类似"最大值最小"这样的字眼就可以往二分法上面去思考,那么怎么来进行二分呢,二分的话肯定是要有单调性的,本题是要怎么划分才可以使各自和的最大值最小,那么如果和越大,我们就可以把更多的数放在一组里面,也就是说组越少,同理,如果和越小,我们可以放在同一组里面的数字肯定就更少,也就是说组越多,这样就找单调性,我们可以二分这个值,这个值的区间是多少呢?显然不能小于数组中的最大值,不能大于数组的和,所以我们就确定了上下界,那么思考怎么如果确定了每一组的最大值,怎么求划分的组数呢?我们贪心的做,从前往后枚举,用一个变量累计和,如果和大于当前二分的值,那么就把前面的枚举的数字当成一组,如果组数小于k,那么说明当前二分的值小了,返回false即可,如果大于等于k,那么说明还是可以往下压缩的,返回true

二分查找 + 贪心

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        function<bool(int)> check = [&](int mid) {
            int sum = 0, res = 1; 
            for (int i = 0; i < nums.size(); i++) {
                if (sum + nums[i] > mid) {
                    res ++;
                    sum = nums[i];
                } 
                else {
                    sum += nums[i];
                }
            }
            return res <= k;
        };

        int l = *max_element(nums.begin(), nums.end());
        int r = accumulate(nums.begin(), nums.end(), 0);
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

时间复杂度: O ( n l o g ( r ? l ) ) O(nlog(r - l)) O(nlog(r?l))

分析

状态定义:我们令f[i][j]表示将前i个数中分成j组,每组和的最大值的最小值

那么状态怎么转移呢?以最后一个不同点为分界点,也就是说,最后一组的起始点,我们可以枚举一下最后一组的起始点,假设当前枚举的是第i个数,要分成j组,最后一组的起始点是u,最后一组的和是sum,那么状态转移方程就是f[i][j] = min(f[i][j], max(f[u - 1][j - 1], sum));状态转移方程出来了,代码就好写了,最初初始化为INFf[0][0] = 0

朴素版 动态规划

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        // 前i个数字中分成j组各自和的最大值的最小值
        vector<vector<int>> f(n + 1, vector<int>(k + 1, 0x3f3f3f3f));
        f[0][0] = 0; 
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= i && j <= k; j ++) {
                int sum = 0;
                for (int u = i; u ; u --) {
                    sum += nums[u - 1];
                    f[i][j] = min(f[i][j], max(f[u - 1][j - 1], sum));
                }
            }
        }
        return f[n][k];
    }
};

时间复杂度: O ( n 2 ? k ) O(n^2 * k) O(n2?k)

动态规划 + 前缀和

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(k + 1, 0x3f3f3f3f));
        vector<int> s(n + 1);
        // 前缀和
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + nums[i - 1]; 
        
        f[0][0] = 0; 
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= i && j <= k; j ++) {
                for (int u = i; u ; u --) {
                    f[i][j] = min(f[i][j], max(f[u - 1][j - 1], s[i] - s[u - 1]));
                }
            }
        }
        return f[n][k];
    }
};

时间复杂度: O ( n 2 ? k ) O(n^2 * k) O(n2?k)

和上面的做法没有本质区别,只是加上了一个前缀和,优化一些计算

文章来源:https://blog.csdn.net/qq_74040620/article/details/135730217
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。