【Leetcode】410. 分割数组的最大值

题目

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

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

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

示例2：
输入：nums = [1,2,3,4,5], k = 2
输出：9

示例3：
输入：nums = [1,4,4], k = 3
输出：4

提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= k <= min(50, nums.length)

思路

这道题我用的方法是二分查找+贪心的做法。这道题目询问的是分组之后最大值的最小情况，这种基本上就是二分的模板的要求，然后再对这个题目进行分析。既然题目要求分组之后最大值尽可能小，那么每一组应该尽可能接近同一个值，假设为x，这就是贪心的思想。

使用贪心算法模拟了数组分割的过程。从数组的开头到结尾进行遍历，利用变量 sum 表示当前分割子数组的和，k 表示需要分割出的子数组的数量（包括当前子数组）。每当 sum 加上当前值超过了某个阈值 x 时，就将当前取的值作为新的一段分割子数组的开头，一直分割 k 次数，一直遍历到最后还没有分割完直接退出。遍历结束后，验证分割 k 次之后数组还有没有未分割的数。这一方法采用贪心策略，每次都选择当前能满足要求的子数组，以尽可能满足题目的条件。

采用二分查找的方法来解决问题。二分查找的上界设定为数组 nums 中所有元素的和，下界为数组 nums 中所有元素的最大值。通过进行二分查找，我们可以找到最小的最大分割子数组和，从而得到最终的答案。这种策略通过二分查找的方式逐步缩小可能的解空间，使得问题得以高效解决。

这里还使用了几个函数来实现，这里简单介绍一下（其实完全没必要只是最近刚学试试）

1.max_element

标准库 头文件中的一个函数模板，用于找到指定范围内的最大元素的迭代器，时间复杂度是 O(n)

用法：

template< class ForwardIt >
ForwardIt max_element( ForwardIt first, ForwardIt last );

first：指向要查找范围的起始位置的迭代器。
last：指向要查找范围的末尾位置的迭代器（不包括末尾位置本身）。
max_element 返回指向范围中最大元素的迭代器。如果范围为空，它将返回 last

2.partial_sum

标准库 头文件中的一个函数模板，用于计算一个范围内元素的部分和，并将结果存储在另一个范围内，时间复杂度是 O(n)

用法：

template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

first：指向要计算范围的起始位置的迭代器。
last：指向要计算范围的末尾位置的迭代器（不包括末尾位置本身）。
d_first：指向存储部分和结果的目标范围的起始位置的迭代器。
partial_sum 将范围 [first, last) 中的元素进行部分和运算，结果存储在以 d_first 为起始位置的目标范围中。

3.upper_bound

upper_bound 函数用于在已排序的区间中查找第一个大于给定值的元素的位置，时间复杂度是O(log n)
用法：

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

first, last：定义查找范围的前开后闭区间，包括 first 但不包括 last。
value：要比较的值。

4.distance

C++ 标准库中的函数，用于计算两个迭代器之间的距离（元素个数），时间复杂度取决于迭代器的类型，随机访问迭代器（如数组、vector 的迭代器），计算距离的操作是常数时间的，时间复杂度为 O(1)。
对于不支持随机访问的迭代器（如链表的迭代器），计算距离需要逐个遍历元素，时间复杂度为 O(N)，其中 N 是两个迭代器之间的距离
用法：

template <class InputIt>
typename iterator_traits<InputIt>::difference_type
distance(InputIt first, InputIt last);

first, last：定义计算距离的范围，包括 first 但不包括 last。
返回值：返回两个迭代器之间的距离（last - first），即元素个数。
注意：该函数适用于任何迭代器类型。

代码

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        vector<int> pre_sum(nums.size() + 1, 0);
        partial_sum(nums.begin(), nums.end(), pre_sum.begin() + 1);

        int left = *max_element(nums.begin(), nums.end());
        int right = accumulate(nums.begin(), nums.end(), 0);

        while (left <= right) {
            int mid = (left + right) >> 1 ;
            int idx = 0;
            for (int i = 0; i < k; ++i) {
                auto it = upper_bound(pre_sum.begin(), pre_sum.end(), mid + pre_sum[idx]);
                idx = distance(pre_sum.begin(), it) - 1;

                if (idx == pre_sum.size() - 1) {
                    break;
                }
            }

            if (idx == pre_sum.size() - 1) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
};

运行结果