Hard
题目描述
你有一艘船，需要将一些箱子从仓库运送到各个港口。船只对箱子数量和总重量都有限制。
给定一个数组 boxes，其中 boxes[i] = [ports_i, weight_i]，以及三个整数 portsCount、maxBoxes 和 maxWeight。
ports_i是第 i 个箱子需要送达的港口weight_i是第 i 个箱子的重量portsCount是港口数量maxBoxes和maxWeight分别是船只的箱子数量和重量限制
箱子必须按照给定顺序运送。船只按以下步骤运行：
- 船只从箱子队列中取一些箱子，不能违反
maxBoxes和maxWeight约束 - 对于每个装载的箱子，船只按顺序前往该箱子需要送达的港口并交付。如果船只已经在正确的港口，则无需旅行，可以立即交付箱子
- 船只返回仓库以从队列中取更多箱子
所有箱子交付完成后，船只必须在仓库结束。
返回船只运送所有箱子到各自港口所需的最少旅行次数。
示例 1：
输入：boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
输出：4
解释：最优策略如下：
- 船只取队列中的所有箱子，前往港口1，然后港口2，再回到港口1，最后返回仓库。4次旅行。
示例 2：
输入：boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
输出：6
约束条件：
1 <= boxes.length <= 10^51 <= portsCount, maxBoxes, maxWeight <= 10^51 <= ports_i <= portsCount1 <= weight_i <= maxWeight
解题思路
这是一个复杂的动态规划问题，需要优化到接近线性时间复杂度。
基本思路：
定义 dp[i] 为运送前 i 个箱子所需的最少旅行次数。对于每个位置 i，我们需要考虑一次运输能载多少箱子（从位置 j 到 i）。
关键观察：
- 一次运输的旅行次数 = 去程旅行次数 + 1（返回仓库）
- 去程旅行次数等于这批箱子中不同港口的数量加上港口切换次数
- 可以预处理前缀和来快速计算重量和港口切换次数
优化思路： 朴素的 O(n²) DP 需要优化。关键在于发现随着右端点增加，可行的左端点范围是单调的。使用单调队列来维护候选的最优转移点，将复杂度降到 O(n)。
具体实现：
- 预处理前缀和数组：重量前缀和、港口切换次数前缀和
- 使用滑动窗口维护当前可行的箱子范围
- 用单调队列优化DP转移，队列中维护可能的最优转移点
- 对于每个位置，先更新队列（移除不可行的点），然后计算当前最优值
这种方法将时间复杂度从 O(n²) 优化到 O(n)，空间复杂度为 O(n)。
代码实现
class Solution {
public:
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.size();
vector<long long> wsum(n + 1, 0); // 重量前缀和
vector<int> tsum(n + 1, 0); // 旅行前缀和
// 预处理前缀和
for (int i = 0; i < n; i++) {
wsum[i + 1] = wsum[i] + boxes[i][1];
if (i > 0 && boxes[i][0] != boxes[i - 1][0]) {
tsum[i + 1] = tsum[i] + 1;
} else {
tsum[i + 1] = tsum[i];
}
}
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
deque<int> dq;
dq.push_back(0);
for (int i = 1; i <= n; i++) {
// 移除不满足重量和数量限制的点
while (!dq.empty() &&
(wsum[i] - wsum[dq.front()] > maxWeight ||
i - dq.front() > maxBoxes)) {
dq.pop_front();
}
if (!dq.empty()) {
int j = dq.front();
dp[i] = dp[j] + tsum[i] - tsum[j + 1] + 2;
}
// 维护单调队列：移除不优的转移点
if (i < n) {
while (!dq.empty() &&
dp[dq.back()] - tsum[dq.back() + 1] >= dp[i] - tsum[i + 1]) {
dq.pop_back();
}
dq.push_back(i);
}
}
return dp[n];
}
};
class Solution:
def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
n = len(boxes)
wsum = [0] * (n + 1) # 重量前缀和
tsum = [0] * (n + 1) # 旅行前缀和
# 预处理前缀和
for i in range(n):
wsum[i + 1] = wsum[i] + boxes[i][1]
if i > 0 and boxes[i][0] != boxes[i - 1][0]:
tsum[i + 1] = tsum[i] + 1
else:
tsum[i + 1] = tsum[i]
dp = [float('inf')] * (n + 1)
dp[0] = 0
from collections import deque
dq = deque([0])
for i in range(1, n + 1):
# 移除不满足重量和数量限制的点
while dq and (wsum[i] - wsum[dq[0]] > maxWeight or
i - dq[0] > maxBoxes):
dq.popleft()
if dq:
j = dq[0]
dp[i] = dp[j] + tsum[i] - tsum[j + 1] + 2
# 维护单调队列：移除不优的转移点
if i < n:
while dq and dp[dq[-1]] - tsum[dq[-1] + 1] >= dp[i] - tsum[i + 1]:
dq.pop()
dq.append(i)
return dp[n]
public class Solution {
public int BoxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.Length;
long[] wsum = new long[n + 1]; // 重量前缀和
int[] tsum = new int[n + 1]; // 旅行前缀和
// 预处理前缀和
for (int i = 0; i < n; i++) {
wsum[i + 1] = wsum[i] + boxes[i][1];
if (i > 0 && boxes[i][0] != boxes[i - 1][0]) {
tsum[i + 1] = tsum[i] + 1;
} else {
tsum[i + 1] = tsum[i];
}
}
int[] dp = new int[n + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
Queue<int> dq = new Queue<int>();
dq.Enqueue(0);
for (int i = 1; i <= n; i++) {
// 移除不满足重量和数量限制的点
while (dq.Count > 0 &&
(wsum[i] - wsum[dq.Peek()] > maxWeight ||
i - dq.Peek() > maxBoxes)) {
dq.Dequeue();
}
if (dq.Count > 0) {
int j = dq.Peek();
dp[i] = dp[j] + tsum[i] - tsum[j + 1] + 2;
}
// 维护单调队列：移除不优的转移点
if (i < n) {
List<int> temp = new List<int>(dq);
dq.Clear();
foreach (int x in temp) {
if (dq.Count == 0 || dp[x] - tsum[x + 1] < dp[i] - tsum[i + 1]) {
dq.Enqueue(x);
}
}
dq.Enqueue(i);
}
}
return dp[n];
}
}
var boxDelivering = function(boxes, portsCount, maxBoxes, maxWeight) {
const n = boxes.length;
const wsum = new Array(n + 1).fill(0); // 重量前缀和
const tsum = new Array(n + 1).fill(0); // 旅行前缀和
// 预处理前缀和
for (let i = 0; i < n; i++) {
wsum[i + 1] = wsum[i] + boxes[i][1];
if (i > 0 && boxes[i][0] !== boxes[i - 1][0]) {
tsum[i + 1] = tsum[i] + 1;
} else {
tsum[i + 1] = tsum[i];
}
}
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
const dq = [0];
for (let i = 1; i <= n; i++) {
// 移除不满足重量和数量限制的点
while (dq.length > 0 &&
(wsum[i] - wsum[dq[0]] > maxWeight ||
i - dq[0] > maxBoxes)) {
dq.shift();
}
if (dq.length > 0) {
const j = dq[0];
dp[i] = dp[j] + tsum[i] - tsum[j + 1] + 2;
}
// 维护单调队列：移除不优的转移点
if (i < n) {
while (dq.length > 0 &&
dp[dq[dq.length - 1]] - tsum[dq[dq.length - 1] + 1] >=
dp[i] - tsum[i + 1]) {
dq.pop();
}
dq.push(i);
}
}
return dp[n];
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n) |
其中 n 是箱子的数量。通过单调队列优化，每个元素最多进出队列一次，因此时间复杂度为线性。