Leetcode題解 SplitArrayLargestSum

2021-01-18 程式設計師大白

點擊上方「程式設計師大白」，選擇「星標」公眾號

重磅乾貨，第一時間送達

題目分析：

給出一串n個數的序列，要求將這n個數分成m個塊，算出每個塊中數的總和，要保證總和的最大值最小。

解題思路：

最小化最大值，顯然是二分搜索結果判斷是否可行，關鍵在於判斷函數的設計。判斷函數可以從另一個角度考慮，假設當前枚舉的最大值是limit，那麼肯定每個塊的最大值都不能超過這個限制。那麼從左到右掃一遍，記錄當前的累加和now，如果掃到第i個數nums[i]的時候，now > sum，說明nums[i]需要放到新的塊中，塊的數目c加一。這樣最後在保證所有塊的總合都小於等於最大值的情況下，看c是否小於等於m，若c <= m，說明還可以繼續二分更小的結果，否則就要二分更大的結果。

算法正確性：

舉例說明：數組序列為[1,3,2,1,5]，要求分成3塊，初始化二分範圍是[5,12]，f(x)為總和最大值不超過x的情況下最少分成幾塊。step 1：l = 5, r = 12, mid = 8, 則f(8) = 2 <= 3.step 2: l = 5, r = 8, mid = 6, 則f(6) = 2 <= 3.step 3: l = 5, r = 6, mid = 5, 則f(5) = 4 > 3.step 4：l = 6, r = 6, l == r, 所以最終結果就是6.每次二分都需要一遍遍歷，這樣算法的複雜度就是O(n * logx)，其中x是數的大小，n是數組長度。


CPP代碼

class Solution {
public:
    using ll = long long;

    bool canSplit(vector<int>& nums, int m, ll limit) {
        ll now = 0;
        int c = 1, cnt = nums.size();
        for (int i = 0; i < cnt; i++) {
            now += nums[i];
            if (now > limit) {
                now = nums[i];
                ++c;
            }
        }
        return c <= m;
    }

    int splitArray(vector<int>& nums, int m) {
        ll l = 0, r = 0;
        int cnt = nums.size();
        for (int i = 0; i < cnt; i++) {
            l = max(l, (ll)nums[i]);
            r += nums[i];
        }
        while (l < r) {
            ll mid = (l + r) >> 1LL;
            if (canSplit(nums, m, mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};
重磅！程式設計師大白交流群-學術微信交流群已成立

額外贈送福利資源！邱錫鵬深度學習與神經網絡，pytorch官方中文教程，利用Python進行數據分析，機器學習學習筆記，pandas官方文檔中文版，effective java（中文版）等20項福利資源
獲取方式：進入群後點開群公告即可領取下載連結

注意：請大家添加時修改備註為 [學校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對話系統。
號主，微商請自覺繞道。謝謝！

推薦閱讀
浙大一教授被指多次性騷擾女博士致其跳樓，校方：缺乏證據
這五款冷門但有趣的Chrome插件，能讓你的瀏覽器好用十倍
955 不加班的公司名單：955.WLB
「拍一拍」 能撤回了 ！！！
5款Chrome插件，第1款絕對良心！

關於程式設計師大白

程式設計師大白是一群哈工大，東北大學，西湖大學和上海交通大學的碩士博士運營維護的號，大家樂於分享高質量文章，喜歡總結知識，歡迎關注[程式設計師大白]，大家一起學習進步！

相關焦點

  • [每日一題]410. Split Array Largest Sum
    給定一個正整數數組nums, 將其分成m個子數組（子數組至少應該有一個元素），那麼每一次分的子數組中的元素求和，會有一個最大值，建設是sum。問題是求所有的分法中，sum最小的值是多少。題目中舉了一個例子。
  • [LeetCode] 918. Maximum Sum Circular Subarray 環形子數組的最大和
    possible sum of a non-empty subarray of C.maximum sum -1Note:-30000<=A[i]<=300001<=A.length<=30000這道題讓求環形子數組的最大和，對於環形數組，我們應該並不陌生，之前也做過類似的題目 Circular Array Loop，就是說遍歷到末尾之後又能回到開頭繼續遍歷。
  • [LeetCode] 976. Largest Perimeter Triangle 最大周長的三角形
    Given an array A of positive lengths, return the largest perimeter of a
  • ​LeetCode刷題實戰53:最大子序和
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 最大子序和，我們先來看題面：https://leetcode-cn.com/problems/maximum-subarray/Given an integer array nums, find the contiguous subarray (containing at least one number
  • [leetcode] 53. Maximum Subarray
    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
  • LeetCode刷題第三周【數組(簡單)】
    參考資料[1]Leetcode網站: https://leetcode-cn.com/[2]以上文字描述均來自 LeetCode數組模塊: https://leetcode-cn.com/tag/array/[3]刷題請點擊或見附錄：1539.
  • [LeetCode] 923. 3Sum With Multiplicity 三數之和的多種情況
    Note:3<=A.length<=30000<=A[i]<=1000<=target<=300這道題是之前那道 3Sum 的拓展，之前那道題是說沒有重複數字，而這道題卻有大量的重複數字，所以每個組合可能會大量重複出現，讓我們統計出所有組合的總出現次數，並對一個超大數取餘。
  • ​LeetCode刷題實戰15題: 三數之和
    今天和大家聊的問題叫做三數之和 ，我們先來看題面：https://leetcode.com/problems/3sum/描述給定一個整數的數組，要求尋找當中所有的a，b，c三個數的組合，使得三個數的和為0.注意，
  • [LeetCode] 912. Sort an Array 數組排序
    ，在平時刷其他題的時候，遇到要排序的時候，一般都會調用系統自帶的排序函數，像 C++ 中直接就調用 sort 函數即可，但是這道題考察的就是排序，再調用系統的排序函數就有些說不過去了。它們的時間複雜度不盡相同，這道題貌似對於平方級複雜度的排序方法會超時，所以只能使用那些速度比較快的排序方法啦。
  • 小張刷題計劃
    原題為了提高自己的代碼能力，小張制定了 LeetCode 刷題計劃，他選中了 LeetCode 題庫中的 n 道題，編號從 0 到 n-1，並計劃在 m 天內按照題目編號順序刷完所有的題目（注意，小張不能用多天完成同一題）。在小張刷題計劃中，小張需要用 time[i] 的時間完成編號 i 的題目。
  • LeetCode數組類知識點&題型總結
    leetcode第一題就是two-sum，對於這類題目，首先看題目要求的時間複雜度和空間複雜度是什麼，其次看有沒有限制條件，如要求不能有重複的子數組或者要求按照升序/降序排列等。= 0;        for (int i = 0;i<nums.length;i++){            sum += nums[i];//每遍歷一次，就把前i次數字相加求和            while (left <=  i && sum >=s){                res =
  • 網際網路公司最常見的面試算法題大集合
    今天新智元給大家推薦的這個GitHub項目，是Repo主自己刷題的心路歷程，並給出了解題參考。/azl397985856/leetcode/blob/master/problems/26.remove-duplicates-from-sorted-array.md🆕 88.merge-sorted-array：https://github.com/azl397985856/leetcode/blob/master/problems/88.merge-sorted-array.md
  • 2019/10/25-LeetCode Array (Day01)
    Maximum SubarrayGiven an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
  • ​LeetCode刷題實戰137:只出現一次的數字 II
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做只出現一次的數字 II，我們先來看題面：https://leetcode-cn.com/problems/single-number-ii/Given an integer array nums where every element appears three times except for one, which appears exactly
  • LeetCode刷題:Array系列之Remove Element
    1、要求Given an array and a value, remove all instances of
  • 最大子序和(Maximum Subarray)
    Maximum Subarray給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。示例:輸入: [-2,1,-3,4,-1,2,1,-5,4]輸出: 6解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
  • [leetcode] 15. 3Sum
  • LeetCode習題解析|2. 3Sum
    下面開始今天的LeetCode習題解析💡原題地址：https://leetcode.com/problems/3sum/題目描述：給定一個數組，找出所有的可能的三個數，使這三個數之和等於0（答案中不能有重複的三元組）
  • [LeetCode] 996. Number of Squareful Arrays 平方數組的個數
    Given an array A of non-negative integers, the array is squareful if for