leetcode
leetcode 1451 ~ 1500
把箱子放进仓库里 II

把箱子放进仓库里 II

难度:

标签:

题目描述

代码结果

运行时间: 109 ms, 内存: 33.7 MB


/*
 * 思路:
 * 1. 先对箱子和仓库的高度进行排序。
 * 2. 从仓库的右边开始放箱子,尝试将尽量大的箱子放入仓库。
 * 3. 如果当前箱子可以放入仓库(即箱子高度小于等于仓库高度),则计数增加。
 */
import java.util.Arrays;
import java.util.Collections;
public class Solution {
    public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
        // 使用Java Stream API
        Arrays.sort(boxes);
        int[] warehouseSorted = Arrays.stream(warehouse)
                                      .boxed()
                                      .sorted(Collections.reverseOrder())
                                      .mapToInt(Integer::intValue)
                                      .toArray();
        int boxIndex = boxes.length - 1;
        int count = 0;
        for (int space : warehouseSorted) {
            if (boxIndex >= 0 && boxes[boxIndex] <= space) {
                count++;
                boxIndex--;
            }
        }
        return count;
    }
}

解释

方法:

这个题解采用了双指针和贪心算法的结合来解决问题。首先对箱子的尺寸进行排序,然后使用两个指针i和j分别指向仓库的左端和右端。算法从两边向中间扫描,尝试放置尽可能大的箱子。每次迭代中,首先找到两个指针位置中仓库的最大高度,然后比较这个高度和最大箱子的尺寸。如果最大箱子不能放入,则将其从列表中移除。如果能放入,根据仓库的高度决定是移动左指针还是右指针,以尽可能利用仓库的空间。这样直到箱子放完或者扫描完仓库的所有位置。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中,为什么需要先对箱子尺寸进行排序?排序的目的和对算法效率的影响是什么?
排序箱子的目的是为了在每次迭代中能够快速决定哪些箱子能够放入仓库。通过将箱子按照大小排序,我们可以从最大的箱子开始尝试,这样一旦发现最大的箱子无法放入,比它小的箱子也肯定无法放入当前位置,从而可以直接移除这些箱子。这种方法减少了每次对箱子适配性的检查次数,提高了算法的效率。排序的时间复杂度为O(n log n),这在整体算法中是可接受的,因为它可以显著减少后续操作的时间复杂度。
🦆
在决定移动左指针还是右指针时,为什么根据仓库的高度而不是其他因素决定?
在决定移动左指针还是右指针时,选择根据仓库的高度来决定是为了最大化箱子的放置。在每次迭代中,通过比较左右两端的高度,移动较高的一端的指针可以保留较低端的空间用于后续可能较小的箱子,这样可以更灵活地利用仓库的空间并尽可能地放入更多的箱子。如果基于其他因素如距离中心的远近来决定指针的移动,可能会导致无法最优地利用仓库的高度差异。
🦆
题解中提到将不能放入的最大箱子移除,这一步是否可能导致其他较小的箱子也无法被放入仓库?
在该算法中,移除不能放入的最大箱子是基于当前仓库最大可用高度的判断。由于箱子已经按大小排序,如果最大的箱子无法放入,那么在该位置所有更大或等于此箱子尺寸的箱子都无法放入。因此,移除这些箱子不会影响到可以放入的较小箱子的判断。这一步是算法贪心策略的一部分,确保每次操作都是在尽可能地放入最大的箱子。
🦆
在仓库的高度差异大时,这种双指针和贪心算法的结合方式仍然适用吗?
在仓库高度差异较大的情况下,这种双指针和贪心算法的结合方式仍然适用,但效果可能会受到一些影响。算法依赖于从两端向中心放置尽可能大的箱子,并尽量利用高度较大的一端。如果高度差异很大,可能会在较低的一端留下较多未利用的空间,因为大箱子无法放入低的一端。在这种情况下,算法仍然可以工作,但可能不是空间利用率最优的方法。对于极端的高度差异,可能需要考虑更复杂的放置策略来优化空间的使用。

相关问题