Question

1564. 把箱子放进仓库里 I

English Version

题目描述

给定两个正整数数组 boxes 和 warehouse ，分别包含单位宽度的箱子的高度，以及仓库中 n 个房间各自的高度。仓库的房间分别从 0 到 n - 1 自左向右编号， warehouse[i] （索引从 0 开始）是第 i 个房间的高度。

箱子放进仓库时遵循下列规则：

• 箱子不可叠放。
• 你可以重新调整箱子的顺序。
• 箱子只能从左向右推进仓库中。
• 如果仓库中某房间的高度小于某箱子的高度，则这个箱子和之后的箱子都会停在这个房间的前面。

你最多可以在仓库中放进多少个箱子？

 

示例 1：

输入：boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
输出：3
解释：

我们可以先把高度为 1 的箱子放入 4 号房间，然后再把高度为 3 的箱子放入 1 号、 2 号或 3 号房间，最后再把高度为 4 的箱子放入 0 号房间。
我们不可能把所有 4 个箱子全部放进仓库里。

示例 2：

输入：boxes = [1,2,2,3,4], warehouse = [3,4,1,2]
输出：3
解释：

我们注意到，不可能把高度为 4 的箱子放入仓库中，因为它不能通过高度为 3 的房间。
而且，对于最后两个房间 2 号和 3 号来说，只有高度为 1 的箱子可以放进去。
我们最多可以放进 3 个箱子，如上图所示。黄色的箱子也可以放入 2 号房间。
交换橙色和绿色箱子的位置，或是将这两个箱子与红色箱子交换位置，也是可以的。

示例 3：

输入：boxes = [1,2,3], warehouse = [1,2,3,4]
输出：1
解释：由于第一个房间的高度为 1，我们只能放进高度为 1 的箱子。

 

提示：

• n == warehouse.length
• 1 <= boxes.length, warehouse.length <= 10^5
• 1 <= boxes[i], warehouse[i] <= 10^9

解法

方法一：预处理 + 排序 + 双指针

我们可以先对仓库的房间进行预处理，得到一个数组 $left$，其中 $left[i]$ 表示下标 $i$ 可以放入的最大箱子高度。

然后对箱子的高度进行排序，从小到大依次放入仓库中。我们使用两个指针 $i$ 和 $j$ 分别指向箱子的第一个位置以及仓库的最后一个位置，如果 $left[j] \lt boxes[i]$，说明当前仓库无法放入箱子 $i$，我们将指针 $j$ 循环向左移动，直到 $left[j] \ge boxes[i]$ 或者 $j \lt 0$。如果此时 $j \lt 0$，说明仓库已经没有空间可以放入箱子 $i$，我们可以直接退出循环。否则说明仓库可以放入箱子 $i$，我们将指针 $i$ 循环向右移动，指针 $j$ 循环向左移动。继续进行上述操作，直到指针 $i$ 超出箱子的范围。

最后我们返回指针 $i$ 的值即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为仓库的房间数。

class Solution:
  def maxBoxesInWarehouse(self, boxes: List[int], warehouse: List[int]) -> int:
    n = len(warehouse)
    left = [warehouse[0]] * n
    for i in range(1, n):
      left[i] = min(left[i - 1], warehouse[i])
    boxes.sort()
    i, j = 0, n - 1
    while i < len(boxes):
      while j >= 0 and left[j] < boxes[i]:
        j -= 1
      if j < 0:
        break
      i, j = i + 1, j - 1
    return i

class Solution {
  public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
    int n = warehouse.length;
    int[] left = new int[n];
    left[0] = warehouse[0];
    for (int i = 1; i < n; ++i) {
      left[i] = Math.min(left[i - 1], warehouse[i]);
    }
    Arrays.sort(boxes);
    int i = 0, j = n - 1;
    while (i < boxes.length) {
      while (j >= 0 && left[j] < boxes[i]) {
        --j;
      }
      if (j < 0) {
        break;
      }
      ++i;
      --j;
    }
    return i;
  }
}

class Solution {
public:
  int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
    int n = warehouse.size();
    int left[n];
    left[0] = warehouse[0];
    for (int i = 1; i < n; ++i) {
      left[i] = min(left[i - 1], warehouse[i]);
    }
    sort(boxes.begin(), boxes.end());
    int i = 0, j = n - 1;
    while (i < boxes.size()) {
      while (j >= 0 && left[j] < boxes[i]) {
        --j;
      }
      if (j < 0) {
        break;
      }
      ++i;
      --j;
    }
    return i;
  }
};

func maxBoxesInWarehouse(boxes []int, warehouse []int) int {
  n := len(warehouse)
  left := make([]int, n)
  left[0] = warehouse[0]
  for i := 1; i < n; i++ {
    left[i] = min(left[i-1], warehouse[i])
  }
  sort.Ints(boxes)
  i, j := 0, n-1
  for i < len(boxes) {
    for j >= 0 && left[j] < boxes[i] {
      j--
    }
    if j < 0 {
      break
    }
    i, j = i+1, j-1
  }
  return i
}

function maxBoxesInWarehouse(boxes: number[], warehouse: number[]): number {
  const n = warehouse.length;
  const left: number[] = new Array(n);
  left[0] = warehouse[0];
  for (let i = 1; i < n; ++i) {
    left[i] = Math.min(left[i - 1], warehouse[i]);
  }
  boxes.sort((a, b) => a - b);
  let i = 0;
  let j = n - 1;
  while (i < boxes.length) {
    while (j >= 0 && left[j] < boxes[i]) {
      --j;
    }
    if (j < 0) {
      break;
    }
    ++i;
    --j;
  }
  return i;
}