410.分割數組的最大值 （二分法）------ 力扣每日打卡Day6

目錄

• • 1.題目
  • 2.題目分析
  • 3.代碼二分法實作
  • 4.總結

1.題目

給定一個非負整數數組和一個整數 m，你需要将這個數組分成 m 個非空的連續子數組。設計一個算法使得這 m 個子數組各自和的最大值最小。

注意:

數組長度 n 滿足以下條件:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

來源：力扣（LeetCode）戳我前往題目

示例:

輸入:
nums = [7,2,5,10,8]
m = 2

輸出:
18

解釋:
一共有四種方法将nums分割為2個子數組。
其中最好的方式是将其分為[7,2,5] 和 [10,8]，
因為此時這兩個子數組各自的和的最大值為18，在所有情況中最小。

           

C語言函數頭：

2.題目分析

一般這種求最小值的，會最先想到動态規劃啥的，但是我技術實在是不精，沒有看懂這動态規劃。這種一看就有很多種分隔方法的題，我們可以換一種思維來做。既然去分組類一個個計算太複雜，就直接找那個最大值。

直接通過二分法找到合适的最大值，然後再帶進數組裡面分隔。

• 分割出來的組數如果小于等于m，那就說明我們找的最大值（mid）偏大，讓right向左收。

• 分割出來的組數如果大于m，那就說明我們找的最大值（mid）偏小，讓left 向右移。

  直到找到最後的mid，就是我們要找的最大值。

3.代碼二分法實作

int count (int* nums, int numsSize, int max){
    int cou = 1;//子數組的個數
    int sum = 0;
    for(int i = 0; i < numsSize; i++){

        //單個數都比最大值大，說明最大數取值太小了，left右移
        if(nums[i] > max){ 
            return INT_MAX;
        }
        
        //比最大值小，就繼續加
        if(nums[i] + sum <= max){
            sum += nums[i];
        }
        
        //如果sum比最大值大，就劃分，進入下一個子數組
        else{ 
            sum = nums[i];
            cou++;
        }
    }
    return cou;
}
int splitArray(int* nums, int numsSize, int m){
    int cou;
    int left = 0,right = INT_MAX;//直接把右設定的int型的最大值
    int mid = (right - left)/2 + left; //也就是我們找的子數組和的最小的最大值
    while(left < right){
        cou = count(nums,numsSize,mid);
        if(cou <= m){ //生成的子數組個數小于等于m,說明我們找的mid太大了，應該向左移
            right = mid;
        }
        else{ //生成的子數組個數大于m,說明我們找的mid太小了，應該右移
            left = mid + 1;
        }
        mid = (right - left)/2 + left;
    }
    return mid;
}
           

4.總結

很多時候這種分割類型、分組的題，因為會有很多種情況，我就看到就想退縮了。記得多換思維，可以直接從結果出發，看起來困難的題，有時候也是很容易的。

不要畏懼他，面對他，側面進攻！加油加油鴨！