Skip to content

Latest commit

 

History

History
231 lines (188 loc) · 7.35 KB

README.md

File metadata and controls

231 lines (188 loc) · 7.35 KB
comments difficulty edit_url tags
true
中等
贪心
数组
排序

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$ 为仓库的房间数。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}