难度: Medium
Submission
运行时间: 109 ms
内存: 33.7 MB
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
boxes.sort()
result, i, j = 0, 0, len(warehouse)-1
while boxes and i <= j:
x = max(warehouse[i], warehouse[j])
while boxes and boxes[-1] > x:
boxes.pop()
if boxes:
result += 1
boxes.pop()
if warehouse[i] > warehouse[j]:
i += 1
else:
j -= 1
return result
Explain
这个题解采用了双指针和贪心算法的结合来解决问题。首先对箱子的尺寸进行排序，然后使用两个指针i和j分别指向仓库的左端和右端。算法从两边向中间扫描，尝试放置尽可能大的箱子。每次迭代中，首先找到两个指针位置中仓库的最大高度，然后比较这个高度和最大箱子的尺寸。如果最大箱子不能放入，则将其从列表中移除。如果能放入，根据仓库的高度决定是移动左指针还是右指针，以尽可能利用仓库的空间。这样直到箱子放完或者扫描完仓库的所有位置。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
boxes.sort() # 对箱子尺寸进行排序
result, i, j = 0, 0, len(warehouse)-1 # 初始化结果和双指针
while boxes and i <= j: # 当还有箱子并且指针未相遇时
x = max(warehouse[i], warehouse[j]) # 取两端仓库高度的较大值
while boxes and boxes[-1] > x:
boxes.pop() # 移除放不下的最大箱子
if boxes: # 如果还有能放的箱子
result += 1 # 结果加1
boxes.pop() # 放入箱子并移除
if warehouse[i] > warehouse[j]:
i += 1 # 根据仓库高度决定移动哪个指针
else:
j -= 1
return result # 返回结果
Explore
排序箱子的目的是为了在每次迭代中能够快速决定哪些箱子能够放入仓库。通过将箱子按照大小排序，我们可以从最大的箱子开始尝试，这样一旦发现最大的箱子无法放入，比它小的箱子也肯定无法放入当前位置，从而可以直接移除这些箱子。这种方法减少了每次对箱子适配性的检查次数，提高了算法的效率。排序的时间复杂度为O(n log n)，这在整体算法中是可接受的，因为它可以显著减少后续操作的时间复杂度。
在决定移动左指针还是右指针时，选择根据仓库的高度来决定是为了最大化箱子的放置。在每次迭代中，通过比较左右两端的高度，移动较高的一端的指针可以保留较低端的空间用于后续可能较小的箱子，这样可以更灵活地利用仓库的空间并尽可能地放入更多的箱子。如果基于其他因素如距离中心的远近来决定指针的移动，可能会导致无法最优地利用仓库的高度差异。
在该算法中，移除不能放入的最大箱子是基于当前仓库最大可用高度的判断。由于箱子已经按大小排序，如果最大的箱子无法放入，那么在该位置所有更大或等于此箱子尺寸的箱子都无法放入。因此，移除这些箱子不会影响到可以放入的较小箱子的判断。这一步是算法贪心策略的一部分，确保每次操作都是在尽可能地放入最大的箱子。
在仓库高度差异较大的情况下，这种双指针和贪心算法的结合方式仍然适用，但效果可能会受到一些影响。算法依赖于从两端向中心放置尽可能大的箱子，并尽量利用高度较大的一端。如果高度差异很大，可能会在较低的一端留下较多未利用的空间，因为大箱子无法放入低的一端。在这种情况下，算法仍然可以工作，但可能不是空间利用率最优的方法。对于极端的高度差异，可能需要考虑更复杂的放置策略来优化空间的使用。