难度: Medium
Submission
运行时间: 92 ms
内存: 35.0 MB
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
boxes.sort()
idx = len(boxes) - 1
ans = 0
for w in warehouse:
while idx >= 0 and boxes[idx] > w:
idx -= 1
if idx < 0:
break
idx -= 1
ans += 1
return ans
Explain
首先对箱子的尺寸进行排序，以确保可以尽可能地将更小的箱子放入仓库中。然后遍历仓库的每个位置，对于每个位置，检查当前最大的箱子是否可以放入（由于已经排过序，所以当前最大的箱子是未被放置的最大箱子）。如果不能放入，则继续检查下一个较小的箱子。如果可以放入，则将该箱子放入仓库，并继续检查下一个仓库的位置。这种方法利用了贪心的策略，旨在每个仓库位置尽可能放入最大的箱子，直到无法放入更多箱子为止。
时间复杂度: O(n log n + n + m) 或简化为 O(n log n + m)
空间复杂度: O(1)
class Solution:
def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
boxes.sort() # 对箱子尺寸进行排序
idx = len(boxes) - 1 # 从最大的箱子开始尝试放置
ans = 0 # 计数可以放进仓库的箱子数
for w in warehouse: # 遍历仓库的每个位置
while idx >= 0 and boxes[idx] > w: # 找到能放入当前仓库位置的最大箱子
idx -= 1 # 如果当前箱子太大，尝试下一个较小的箱子
if idx < 0: # 如果没有更多箱子可以考虑，终止循环
break
idx -= 1 # 放入箱子后，索引减一，准备放下一个箱子
ans += 1 # 成功放入一个箱子，计数加一
return ans # 返回总能放入的箱子数
Explore
贪心算法被选择用于解决这个问题因为它简单且高效，能快速地找到可行解。在此场景中，贪心算法通过尝试在每个仓库位置放入当前能放的最大箱子，来达到尽可能多地使用仓库空间。然而，贪心算法并不总是能得到最优解。它只保证在每一步做出局部最优选择，但这些选择可能不会导致全局最优解。尽管如此，在许多实际情况下，贪心算法提供的解决方案足够接近最优，特别是在一些特定约束和规则下。
代码中确实没有显式地处理仓库中高度不一的问题，因为它通过遍历每个仓库位置，并尝试在每个位置放入当前可用的最大箱子来间接处理高度问题。遍历过程中，如果当前位置的高度不允许放入最大箱子，则会尝试下一个较小的箱子。这种方法隐式地适应了仓库各位置的高度变化，无需额外的高度调整逻辑。
是的，这种方法可能会错过某些特殊情况下的最佳放置策略。因为一旦决定一个较大的箱子无法放入，就立即检查下一个较小的箱子，这可能导致忽略了在后续仓库位置可能适合放入较大箱子的情况。这种策略优先保证当前位置被填充，但不一定能保证整体的最优填充效果。
如果中断循环的处理是在确定没有更多箱子可用时进行的，那么不会错过检查有效的仓库位置。代码中的循环确保了每个仓库位置都被检查，直到没有更多的箱子可以放入。因此，在所有箱子都尝试过后，循环才会中断，确保不会有仓库位置未被检查。