从仓库到码头运输箱子

标签: 线段树 队列 数组 动态规划 前缀和 单调队列 堆（优先队列）

难度: Hard

你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。

给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [ports​​i​, weighti] 。

  • ports​​i 表示第 i 个箱子需要送达的码头， weightsi 是第 i 个箱子的重量。
  • portsCount 是码头的数目。
  • maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。

箱子需要按照 数组顺序 运输，同时每次运输需要遵循以下步骤：

  • 卡车从 boxes 队列中按顺序取出若干个箱子，但不能违反 maxBoxes 和 maxWeight 限制。
  • 对于在卡车上的箱子，我们需要 按顺序 处理它们，卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头，那么不需要 额外行程 ，箱子也会立马被卸货。
  • 卡车上所有箱子都被卸货后，卡车需要 一趟行程 回到仓库，从箱子队列里再取出一些箱子。

卡车在将所有箱子运输并卸货后，最后必须回到仓库。

请你返回将所有箱子送到相应码头的 最少行程 次数。

示例 1：

输入：boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
输出：4
解释：最优策略如下：
- 卡车将所有箱子装上车，到达码头 1 ，然后去码头 2 ，然后再回到码头 1 ，最后回到仓库，总共需要 4 趟行程。
所以总行程数为 4 。
注意到第一个和第三个箱子不能同时被卸货，因为箱子需要按顺序处理（也就是第二个箱子需要先被送到码头 2 ，然后才能处理第三个箱子）。

示例 2：

输入：boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
输出：6
解释：最优策略如下：
- 卡车首先运输第一个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第二、第三、第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五个箱子，到达码头 2 ，回到仓库，总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。

示例 3：

输入：boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
输出：6
解释：最优策略如下：
- 卡车运输第一和第二个箱子，到达码头 1 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第三和第四个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五和第六个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
总行程数为 2 + 2 + 2 = 6 。

示例 4：

输入：boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
输出：14
解释：最优策略如下：
- 卡车运输第一个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第二个箱子，到达码头 2 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第三和第四个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第五个箱子，到达码头 3 ，然后回到仓库，总共 2 趟行程。
- 卡车运输第六和第七个箱子，到达码头 3 ，然后去码头 4 ，然后回到仓库，总共 3 趟行程。
- 卡车运输第八和第九个箱子，到达码头 1 ，然后去码头 5 ，然后回到仓库，总共 3 趟行程。
总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。

提示：

  • 1 <= boxes.length <= 105
  • 1 <= portsCount, maxBoxes, maxWeight <= 105
  • 1 <= ports​​i <= portsCount
  • 1 <= weightsi <= maxWeight

Submission

运行时间: 298 ms

内存: 57.0 MB

class Solution:
    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
        n = len(boxes)
        weight_prefix_sums = list(accumulate([weight for _, weight in boxes], initial = 0))
        diff_cnts = [0] * (n + 1)
        for i in range(1, n):
            diff_cnts[i + 1] = (boxes[i][0] != boxes[i - 1][0]) + diff_cnts[i]
        q = deque([0])
        f, g = [0] * (n + 1), [0] * (n + 1)
        for i in range(1, n + 1):
            while i - q[0] > maxBoxes or weight_prefix_sums[i] - weight_prefix_sums[q[0]] > maxWeight:
                q.popleft()
            f[i] = g[q[0]] + diff_cnts[i] + 2
            if i != n:
                g[i] = f[i] - diff_cnts[i + 1]
                while q and g[i] <= g[q[-1]]:
                    q.pop()
                q.append(i)
        return f[n]

Explain

这个问题可以通过动态规划和滑动窗口的方法解决。我们定义 f[i] 为到第 i 个箱子（包括第 i 个箱子）的最少行程次数。我们还需要一个辅助数组 g[i]，g[i] = f[i] - diff_cnts[i]，这里 diff_cnts[i] 记录从第 1 个箱子到第 i 个箱子需要停靠的码头数。我们使用一个双端队列 q 来维护可能的最小 g 值的索引，这样可以在 O(1) 时间内得到滑动窗口中的最小值。队列 q 保证了它的元素是递增的，确保了每次从队列头部取出的元素都是给定条件下的最小行程数。我们更新 f[i] 为 g[q[0]] + diff_cnts[i] + 2，其中 2 代表从仓库到第一个箱子的码头和从最后一个箱子的码头返回仓库的行程。随着 i 的增加，我们不断更新队列，确保它符合 maxBoxes 和 maxWeight 的限制。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
        n = len(boxes)
        # 前缀和数组，记录到当前箱子为止的总重量
        weight_prefix_sums = list(accumulate([weight for _, weight in boxes], initial=0))
        # 差异计数，记录到当前箱子为止，需要停靠的码头数量
        diff_cnts = [0] * (n + 1)
        for i in range(1, n):
            diff_cnts[i + 1] = (boxes[i][0] != boxes[i - 1][0]) + diff_cnts[i]
        # 双端队列，用于维护滑动窗口内的最小 g 值的索引
        q = deque([0])
        f, g = [0] * (n + 1), [0] * (n + 1)
        for i in range(1, n + 1):
            # 维护滑动窗口，确保不超过 maxBoxes 和 maxWeight
            while i - q[0] > maxBoxes or weight_prefix_sums[i] - weight_prefix_sums[q[0]] > maxWeight:
                q.popleft()
            # 计算当前的最少行程次数
            f[i] = g[q[0]] + diff_cnts[i] + 2
            if i != n:
                g[i] = f[i] - diff_cnts[i + 1]
                # 维护队列，保持其单调性
                while q and g[i] <= g[q[-1]]:
                    q.pop()
                q.append(i)
        return f[n]

Explore

在这个问题中，我们需要找到最少的行程次数来运输所有箱子。动态规划是一个强大的方法，用于解决这类优化问题，它可以帮助我们通过建立子问题的解来逐步构建整个问题的解。滑动窗口方法则用于优化动态规划的过程，通过维护一个滑动窗口来限制考虑的状态范围，从而减少不必要的计算和空间消耗。这样结合使用，可以在保证找到最优解的同时，显著提高算法的效率。

双端队列是此问题中的理想选择，因为它能够支持从两端进行高效的元素添加和删除操作，这对于维护滑动窗口中的状态非常关键。使用双端队列可以在常数时间内获取当前窗口的最小值（队首元素），同时能够快速地从队尾添加新元素和从队首移除过时元素。相比之下，堆虽然可以快速访问最小元素，但删除特定元素的操作较慢；红黑树提供了平衡的性能，但其操作复杂度和实现难度高于双端队列。

在构建diff_cnts数组时，第一个箱子之前没有其他箱子可以比较，因此diff_cnts数组在第一个位置（也就是diff_cnts[1]）设置为0。对于之后的每个箱子，我们检查当前箱子与前一个箱子的码头是否相同，如果不同，则在前一个箱子的diff_cnts值基础上加1，反映了需要多停靠一个码头。这样可以确保每个箱子的码头变化都被正确地累加计算。

在题解中加上的2代表的是两段固定的行程：从仓库到第一个箱子的码头的行程，以及从最后一个箱子的码头返回仓库的行程。这两段行程是每次运输过程中不可避免的，因此无论实际的箱子如何分配和运输，这两段行程总是存在的。因此，在计算任何一次独立的运输行程（即f[i]）时，都需要额外加上这两次行程，故加2。