What pattern is used in Delivering Boxes from Storage to Ports?

The problem uses state transition dynamic programming with sequential dependency and batch evaluation under constraints.

How do I handle maxBoxes and maxWeight constraints?

Precompute prefix sums for box counts and weights to quickly check if a batch exceeds limits before updating DP.

Why is monotonic queue useful in this problem?

It efficiently maintains candidate batch starting points for DP, removing invalid options and reducing overall complexity.

Can boxes be delivered out of order?

No, the boxes must be delivered in order, which is essential for the DP transitions to be correct.

What is the time complexity after optimization?

After prefix sums and monotonic queue optimization, the DP approaches O(n) time complexity with O(n) space.

#1687

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

从仓库到码头运输箱子

你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有箱子数目的限制和总重量的限制。给你一个箱子数组 boxes 和三个整数 portsCount , maxBoxes 和 maxWeight ，其中 boxes[i] = [ports i , weight…

数组动态规划线段树队列堆（优先队列）

题目描述

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

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

ports_i 表示第 i 个箱子需要送达的码头， weights_i 是第 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 <= 10⁵
1 <= portsCount, maxBoxes, maxWeight <= 10⁵
1 <= ports_i <= portsCount
1 <= weights_i <= maxWeight

lightbulb

解题思路

方法一：动态规划 + 单调队列优化

我们定义 $f[i]$ 表示把前 $i$ 个箱子从仓库运送到相应码头的最少行程数，那么答案就是 $f[n]$ 。

箱子需要按数组顺序运输，每一次运输，卡车会按顺序取出连续的几个箱子，然后依次送往对应的码头，全部送达之后，又回到了仓库。

因此，我们可以枚举上一次运输的最后一个箱子的编号 $j$ ，那么 $f[i]$ 就可以从 $f[j]$ 转移而来，转移的时候，我们需要考虑以下几个问题：

从 $f[j]$ 转移过来的时候，卡车上的箱子数量不能超过 $maxBoxes$
从 $f[j]$ 转移过来的时候，卡车上的箱子总重量不能超过 $maxWeight$

状态转移方程为：

f[i] = \min_{j \in [i - maxBoxes, i - 1]} \left(f[j] + \sum_{k = j + 1}^i \textit{cost}(k)\right)

其中 $\sum_{k = j + 1}^i \textit{cost}(k)$ 表示通过一次运输，把 $[j+1,..i]$ 这些箱子送往对应的码头所需要的行程数。这部分行程数可以通过前缀和快速计算出来。

简单举个例子，假设我们取出了 $1, 2, 3$ 这三个箱子，需要送往 $4, 4, 5$ 这三个码头，那么我们首先要从仓库到 $4$ 号码头，然后再从 $4$ 号码头到 $5$ 号码头，最后再从 $5$ 号码头回到仓库。可以发现，从仓库到码头，以及从码头到仓库，需要花费 $2$ 趟行程，而从码头到码头的行程数，取决于相邻两个码头是否相同，如果不相同，那么行程数会增加 $1$ ，否则不变。因此，我们可以通过前缀和，计算出码头之间的行程数，再加上首尾两趟行程，就能把 $[j+1,..i]$ 这些箱子送往对应的码头所需要的行程数计算出来。

代码实现如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 33/39 个通过测试用例，超出时间限制
class Solution:
    def boxDelivering(
        self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int
    ) -> int:
        n = len(boxes)
        ws = list(accumulate((box[1] for box in boxes), initial=0))
        c = [int(a != b) for a, b in pairwise(box[0] for box in boxes)]
        cs = list(accumulate(c, initial=0))
        f = [inf] * (n + 1)
        f[0] = 0
        for i in range(1, n + 1):
            for j in range(max(0, i - maxBoxes), i):
                if ws[i] - ws[j] <= maxWeight:
                    f[i] = min(f[i], f[j] + cs[i - 1] - cs[j] + 2)
        return f[n]

本题数据规模达到 $10^5$ ，而以上代码的时间复杂度为 $O(n^2)$ ，会超出时间限制。我们仔细观察：

f[i] = \min(f[i], f[j] + cs[i - 1] - cs[j] + 2)

实际上我们是要在 $[i-maxBoxes,..i-1]$ 这个窗口内找到一个 $j$ ，使得 $f[j] - cs[j]$ 的值最小，求滑动窗口的最小值，一种常用的做法是使用单调队列，可以在 $O(1)$ 时间内获取到满足条件的最小值。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是题目中箱子的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

speed

复杂度分析

指标	值
时间	complexity depends on the optimization: naive DP is O(n^2), prefix sums reduce some overhead, and monotonic queue optimization approaches O(n). Space complexity is O(n) for storing dp array and prefix sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion of state transition dynamic programming patterns with sequential dependencies.
question_mark
Look for handling multiple constraints: maxBoxes, maxWeight, and ordered delivery.
question_mark
Interest in reducing naive O(n^2) DP via prefix sums or monotonic structures.

warning

常见陷阱

外企场景

error
Failing to respect the delivery order of boxes when forming DP batches.
error
Overlooking the cumulative weight and box limits when computing each batch.
error
Incorrectly counting trips when consecutive boxes go to the same port.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow boxes to be delivered out of order, which changes DP formulation significantly.
arrow_right_alt
Introduce variable ship capacity per trip, requiring dynamic adjustment in DP batch evaluation.
arrow_right_alt
Optimize for cases where portCount is very large relative to boxes, leveraging sparse updates.

help

常见问题

外企场景

继续练习

#1696 跳跃游戏 VI #1425 带限制的子序列和 #2398 预算内的最多机器人数目