1011. 在 D 天内送达包裹的能力

二分查找 + 贪心

解题思路

  1. 可以用于查找一个 有范围的 整数，就能想到是不是可以使用二分查找去解决这道问题；

  2. 这道题是对结果的二分，同 leetcode🧑‍💻 410. 分割数组的最大值 题解一致，只是换了种方式表达；

复杂度

  1. 时间复杂度：O(nlog⁡(sum − maxn))，其中 sum 表示数组 weights 中所有元素的和，maxn 表示数组所有元素的最大值；每次二分查找时，需要对数组进行一次遍历，时间复杂度为 O(n)

  2. 空间复杂度：O(1)

代码实现

var shipWithinDays = function (weights, days) {
    let left = Math.max(...weights);
    let right = weights.reduce((sum, curr) => sum += curr, 0);

    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);

        let cnt = check(weights, mid);
        if (cnt > days) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
};

function check(weights, maxIntervalSum) {
    let cnt = 1;
    let sum = 0;

    for (const w of weights) {
        if (sum + w > maxIntervalSum) {
            cnt++;
            sum = 0;
        }
        sum += w;
    }

    return cnt;
}

动态规划

解题思路

复杂度

代码实现

// 先欠着
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 二分查找 + 贪心
    1. 1.1. 解题思路
    2. 1.2. 复杂度
    3. 1.3. 代码实现
  2. 2. 动态规划
    1. 2.1. 解题思路
    2. 2.2. 复杂度
    3. 2.3. 代码实现