410. 分割數組的最大值

思路

要將陣列分割成 $k$個非空的子陣列，並找到一個分割方法，能使子陣列的總和最大值最小。
比如陣列 $[1,2,3,4,5],k=2$ ，最好的分法是 $[1,2,3],~[4,5]$，子陣列的總和分別是 $6,~9$，
最大值是 $9$，是所有分割方案當中最小的。

假如不管 $k$ 的限制，在陣列 $[1,2,3,4,5]$ 當中。

• 最糟糕的子陣列總和，就是陣列本身的總和 15。
• 最佳的子陣列總和，就是把陣列徹底拆了，取最大值，為 5。

現在加上了 $k$ 的限制，最糟糕的答案不會比 15 更高，也不會比 5 更低，我們找到了最後答案的上界與下界。
接下來試著用二分的方式猜答案，mid = 10，要怎麼驗證這個答案呢？

這時的mid代表子陣列總和的最大值，想要驗證這個答案合不合理， 就去看能不能把陣列切成幾個總和不超過mid的子陣列，假如沒辦法在mid的限制下將陣列切成 $\leq{k}$ 份，mid就是不合理的答案。

• mid = 10，可切割成 $[1,2,3],~[4,5]$，更新邊界為 5, 9（閉區間）
• mid = 7，只能切成 $[1,2,3],[4],[5]$，更新邊界 8, 9
• mid = 8，只能切成 $[1,2,3],[4],[5]$，更新邊界 9, 9
• mid = 9，可切割成 $[1,2,3],~[4,5]$，更新邊界 9, 8，觸發終止條件，

程式碼

二分答案

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int left = 0, right = 0;
        for(int x : nums) {
            left = max(left, x);
            right += x;
        }
        
        auto check = [&](int limit) -> bool {
            int cnt = 1;
            int sum = 0;
            for(int x : nums) {
                if(sum + x > limit) {
                    cnt++;
                    sum = x;
                }
                else {
                    sum += x;
                }
            }
            return cnt <= k; // 能不能分割成 <= k 個數組
        };

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(check(mid)) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return left;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$