線上面試，最后面試官說從力扣上隨便找一道題讓我做一下，屏幕共享，直接在力扣網(wǎng)站上做。

原題鏈接:https://leetcode.cn/problems/split-array-largest-sum/description/?envType=problem-list-v2&envId=greedy

題目如下:

給定一個非負(fù)整數(shù)數(shù)組 nums 和一個整數(shù) k ，你需要將這個數(shù)組分成 k 個非空的連續(xù)子數(shù)組。

設(shè)計(jì)一個算法使得這 k 個子數(shù)組各自和的最大值最小。

示例 1：

輸入：nums = [7,2,5,10,8], k = 2

輸出：18

解釋：

一共有四種方法將 nums 分割為 2 個子數(shù)組。
其中最好的方式是將其分為 [7,2,5] 和 [10,8] 。
因?yàn)榇藭r這兩個子數(shù)組各自的和的最大值為 18，在所有情況中最小。
示例 2：

輸入：nums = [1,2,3,4,5], k = 2

輸出：9

示例 3：

輸入：nums = [1,4,4], k = 3

輸出：4

首先我在讀題上有遺漏，顯示忽略了"連續(xù)"兩個字，思路奔著切分出的數(shù)組有 k 個元素，然后求所有切分?jǐn)?shù)組中元素加起來和最大的那個

然后又有nums.length/k | 0,搞成了每個數(shù)組里有 k 個元素，最后卡在了怎么把數(shù)組切分出 k 個，最后才注意到各自的和的最大值

這里我介意力扣補(bǔ)充一下不對的情況為啥不對，對比起來能更好的理解題意，當(dāng)然這次是我太毛躁了。

誠然把數(shù)組分成 k 這個也是有辦法的，比如 k-1 個 for 循環(huán)搞出 k-1 個數(shù)組下標(biāo)，再進(jìn)行分組，但是這樣要所有循環(huán)都完成才知道哪個是最佳答案,我是寫文章的時候想到的

這篇文章提供了更好的思路:https://segmentfault.com/a/1190000023373836

反過來我們可以從最佳答案入手，一定是在數(shù)組元素的最大值，和數(shù)組所有的元素總和之間，在加上二分查找法。

最終答案通過了力扣所有的用例,如下:

var splitArray = function (nums, k) {
        let minCount = 0,
          maxCount = 0;
        nums.forEach((item) => {
          maxCount += item;
          if (item > minCount) {
            minCount = item;
          }
        });

        if (k == 1) {
          return maxCount;
        }

        while (minCount < maxCount) {
          let midCount = ((minCount + maxCount) / 2) | 0;
          let sum = 0;
          splitCount = 0;

          nums.forEach((item, i) => {
            if (sum + item > midCount) {
              splitCount++;
              sum = 0;
            }
            sum += item;
          });
          splitCount++;

          if (splitCount > k) {
            minCount = midCount + 1;
          } else {
            maxCount = midCount;
          }
        }
        return minCount;
      };

求出數(shù)組中最大元素minCount,和數(shù)組中所有元素之和maxCount

 nums.forEach((item) => {
          maxCount += item;
          if (item > minCount) {
            minCount = item;
          }
        });

如果 k=1 就沒必要繼續(xù)下去，只分一個數(shù)組，直接返回maxCount

if (k == 1) {
          return maxCount;
        }

使用二分查找，先取中間值midCount,sum是子數(shù)組元素的總和,splitCount是分了幾個數(shù)組

while (minCount < maxCount) {
          let midCount = ((minCount + maxCount) / 2) | 0;
          let sum = 0;
          splitCount = 0;

如果sum加上數(shù)組當(dāng)前元素item的值超出了midCount，說明該分組了，這個時候分組個數(shù)splitCount加一，sum重置為零

nums.forEach((item, i) => {
            if (sum + item > midCount) {
              splitCount++;
              sum = 0;
            }
            sum += item;
          });

一開始沒有這行代碼，有一個用例沒通過，以nums = [7,2,5,10,8], k = 2 為例 7+2=9,9+5=14,14+10>21,此時splitCount是 1,0+10 = 10 10+8=18，到了數(shù)組最后一個元素后退出，其實(shí)是分了兩組的

splitCount++;

此時已經(jīng)是[7,2,5]、[10,8]的分法了，可是midCount是 21,我有在后面直接加

if(splitCount == k){
    return midCount
}

也是有用例不通過，但其實(shí)子數(shù)組中所有元素值和最大的是 18,按照最終答案我加來一個打印

        while (minCount < maxCount) {
          let midCount = ((minCount + maxCount) / 2) | 0;
          console.log({minCount, midCount, maxCount});

輸出如下:

{minCount: 10, midCount: 21, maxCount: 32}

{minCount: 10, midCount: 15, maxCount: 21}

{minCount: 16, midCount: 18, maxCount: 21}

{minCount: 16, midCount: 17, maxCount: 18}

也就是最后minCount = midCount + 1;導(dǎo)致while (minCount < maxCount)不成立，最后返回minCount得出結(jié)論，這一步我還不是很理解，

但有一說一，這種算法最多應(yīng)用還是在面試，實(shí)際工作中我還真沒遇到過，我建議還是多和業(yè)務(wù)場景掛鉤。