题解

这里题解我就不写了，给大家贴上两篇写的不错的题解，大家可以结合来看,是看y总讲解写的题解
题解1
题解2

记录困扰我的几个问题

仅仅表示我的理解，可能有问题，如果有问题请大家指出，会尽快修改，避免误人子弟

1. 为什么单调队列最开始要添加一个0

   填充个0为了方便我们计算前几项，因为前几项的上一次运送货物的右端点是  0 ~ i-1, 
   我们需要用到 f[0],所以需要添加
   

2. !minDeque.isEmpty() && minDeque.peekFirst() < j - 1这里为什么是小于 j -1

   这是因为我们每次计算f[i]是根据上一次运送货物的结尾k 加上 cost(k, i)左开右闭, 而上次
   的取值是 j -1 ~ i - 1 所以这里是小于 j - 1, 它超出了我们上次运送货物右端点的最小值

3. 维护单调队列判断出队是， cost的右端点为什么是i+1

   大家可以参考y总画的图，在右端点大于右边那个点时，无论右端点取到哪里，两者的差值都是固定的。
   为了方便，我们可以直接取i+1就好了，但是要将前缀和数组多开一个，同时令 sum[n+1] = sum[n]

最后贴上我的Java代码，因为使用原生api，所以效率不高，为了效率大家可以用数组自己维护个单调队列

    int[] sum; // 分界点得前置和数组

    public int cost(int i, int j) { // 我这里写的cost是左开右闭区间得
        if (sum[i+1] == sum[i]) { // i点不是分界点
            return sum[j] - sum[i] + 1;
        } else {
            return sum[j] - sum[i];
        }
    }
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        int n = boxes.length;
        sum = new int[n+2]; // 分界点得前置和数组
        int[] f = new int[n+1]; // fi表示前i个货物完成运输得最小路程

        Deque<Integer> minDeque = new LinkedList<>();
        for (int i = 1; i <= n; i++) { // 分界点前缀和数组填充
            sum[i] = sum[i-1];
            if (i == 1 || boxes[i-1][0] != boxes[i-2][0]) {
                sum[i] += 1;
            }
        }
        sum[n+1] = sum[n]; // cover一下n+1
        minDeque.offerLast(0); // 填充0，这是为了方便计算第一项,
        // j 表示能满足装货物条件最早得位置, w 表示当前总重量
        // 而上一次运送最右端的取值就是 j - 1 ~ i - 1
        for (int i = 1, j = 1, w = 0; i <= n; i++) {
            w += boxes[i-1][1];
            while (i - j + 1 > maxBoxes || w > maxWeight) { // 如果长度或者体重超出限制，就要让最前面得货物出队,缩小区间
                w -= boxes[j-1][1];
                j++;
            }
            while (!minDeque.isEmpty() && minDeque.peekFirst() < j - 1) minDeque.pollFirst(); // 让超出上一次运送的货物出队
            int k = minDeque.peekFirst();
            f[i] = f[k] + cost(k, i) + 1; // 这个k就表示这个区间中(j - i)，选择k为分开运输得点得代价最小

            // 对于新的 i 点，要进行单调队列优化， 比较队列末尾的点 a 和 当前这个点 i哪个更好
            while (!minDeque.isEmpty() &&
                    f[minDeque.peekLast()] >
                            f[i] + cost(i, i+1) - cost(minDeque.peekLast(), i+1))
                minDeque.pollLast();
            minDeque.offerLast(i);
         }

        return f[n];
    }