题目描述
leetcode 困难题
你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [portsi, weighti] 。
portsi 表示第 i 个箱子需要送达的码头， weightsi 是第 i 个箱子的重量。
portsCount 是码头的数目。
maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。
箱子需要按照 数组顺序 运输，同时每次运输需要遵循以下步骤：
卡车从 boxes 队列中按顺序取出若干个箱子，但不能违反 maxBoxes 和 maxWeight 限制。
对于在卡车上的箱子，我们需要 按顺序 处理它们，卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头，那么不需要 额外行程 ，箱子也会立马被卸货。
卡车上所有箱子都被卸货后，卡车需要 一趟行程 回到仓库，从箱子队列里再取出一些箱子。
卡车在将所有箱子运输并卸货后，最后必须回到仓库。
请你返回将所有箱子送到相应码头的 最少行程 次数。
示例1：
1
2
3
4
5
6
7
| 输入：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 。
|
提示1：
1
2
3
4
| 1 <= boxes.length <= 10^5
1 <= portsCount, maxBoxes, maxWeight <= 10^5
1 <= portsi <= portsCount
1 <= weightsi <= maxWeight
|
动态规划
以下前缀和或 $dp$ 数组为了方便下标都从 $1$ 开始到 $n$ 结束。
定义 $w$ 为重量前缀和数组；$diff$ 为“相邻不相等码头”前缀和数组，即 $diff[j]$ 表示 $[0, j]$ 区间箱子的相邻不相等码头的和。
利用 $diff$ 可以 $O(1)$ 的求出一趟车的最小行程，设该趟车第一个箱子为 $x$ ，最后一个箱子为 $y$ ，那么该趟的最小行程为 $diff[y] - diff[x] + 2$，其中 $2$ 是因为汽车离开仓库和返回仓库所消耗行程。
定义 $dp[i]$ 表示 $[0, i - 1]$ 区间箱子的最少行程数，$i - 1$ 显然为某趟车的最后一个箱子下标，那么 $dp[n]$ 为答案。
具体转移过程如下，对于每个 $dp[i]$，枚举上一趟车最后一个箱子的可能性 $dp[j]$，那么其在 $boxes$ 中的下标为 $j - 1$ ，也就是说 $j$ 为该趟车第一个箱子，简略的转移方程为：
$$
\begin{align}
&dp(i) = max(dp[j] + diff[i - 1] - diff[j] + 2) max(0, i - maxBoxes) <= j < i\\
\end{align}
$$
该解法时间复杂度为 $O(N^2)$ ，会 TLE 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
int[] w = new int[n + 1];
int[] diff = new int[n + 1];
for(int i = 1; i < n + 1; i++){
w[i] = w[i - 1] + boxes[i - 1][1];
diff[i] = i == n || boxes[i - 1][0] == boxes[i][0] ? diff[i - 1] : diff[i - 1] + 1;
}
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i < n + 1; i++){
for(int j = Math.max(0, i - maxBoxes); j < i; j++){
if(w[i] - w[j] > maxWeight){
continue;
}
dp[i] = Math.min(dp[i], dp[j] + diff[i - 1] - diff[j] + 2);
}
}
return dp[n];
}
}
|
动态规划 + 单调队列
观察上面的转移过程可知，内层循环实际上是在 $[max(0, i - maxBoxes), i - 1]$ 窗口内找到一个满足要求的 $dp[j] - diff[j]$ 最小值，所以我们可以利用单调队列来实现 $O(1)$ 获取最小值。
每个下标最多进队一次出队一次，内层最多总共循环 $n$ 次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
int[] w = new int[n + 1];
int[] diff = new int[n + 1];
for(int i = 1; i < n + 1; i++){
w[i] = w[i - 1] + boxes[i - 1][1];
diff[i] = i == n || boxes[i - 1][0] == boxes[i][0] ? diff[i - 1] : diff[i - 1] + 1;
}
int[] dp = new int[n + 1];
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(0);
for(int i = 1; i < n + 1; i++){
while(!deque.isEmpty() && (i - deque.peekFirst() > maxBoxes || w[i] - w[deque.peekFirst()] > maxWeight)){
deque.pollFirst();
}
int min = deque.peekFirst();
dp[i] = dp[min] + diff[i - 1] - diff[min] + 2;
while(!deque.isEmpty() && (dp[i] - diff[i] < dp[deque.peekLast()] - diff[deque.peekLast()])){
deque.pollLast();
}
deque.offerLast(i);
}
return dp[n];
}
}
|