# LEETCODE 1564. Put Boxes Into the Warehouse I 解题思路分析

Given two arrays of positive integers `boxes` and `warehouse` representing the heights of some boxes of unit width, and the heights of `n` rooms in a warehouse, respectively. The warehouse’s rooms are labeled from `0` to `n - 1` from left to right where `warehouse[i]` (0-indexed) is the height of the `ith` room.

Boxes are put into the warehouse by the following rules:

• Boxes can’t be piled up.
• You can rearrange the order of the boxes.
• Boxes can only be pushed into the warehouse from left to right only.
• If the height of some room in the warehouse is less than the height of a box, then the box will be stopped before that room, so are the boxes behind it.

Return the maximum number of boxes you can put into the warehouse.

```输入: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]

We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0. There is no way we can fit all 4 boxes in the warehouse.```

```输入: boxes = [1,2,2,3,4], warehouse = [3,4,1,2]

Notice that it's not possible to put the box of height 4 into the warehouse since it cannot pass the first room of height 3. Also, for the last two rooms, 2 and 3, only boxes of height 1 can fit. We can fit 3 boxes maximum as shown above. The yellow box can also be put in room 2 instead. Swapping the orange and green boxes is also valid, or swapping one of them with the red box.```

Example 3:

```Input: boxes = [1,2,3], warehouse = [1,2,3,4]
Output: 1
Explanation: Since the first room in the warehouse is of height 1, we can only put boxes of height 1.
```

Example 4:

```Input: boxes = [4,5,6], warehouse = [3,3,3,3,3]
Output: 0
```

Constraints:

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

1. 我们需要先对数据进行预处理，即算出仓库的每一个位置上到入口间的最小高度，即leftMinHeight[i]表示下标0到i间的最小高度。计算这个高度很简单，我们使用一个循环，从仓库下标0循环至末尾。下标0处，leftMinHeight[0]等于仓库位置0处的高度warehouse[0]，而其他位置leftMinHeight[i]则等于: min(warehouse[i],leftMinHeight[i-1])
2. 接下来我们对箱子按照高度进行排序
3. 将当前箱子尽量向仓库的右边放。即使用双指针，初始时，箱子指针指向下标0（高度最小的箱子），仓库指针指向仓库最右端。如果当前箱子的高度小于等于leftMinHeight[i]，即，当前箱子可以从入口移动到仓库当前位置，此时，返回结果加一，同时箱子指针向右移动一位，仓库指针向左移动一位。反之，代表当前箱子无法顺利移动到仓库当前位置，那么，我们只能将仓库位置向左移动一位。重复上述操作，直到仓库位置小于0，或者箱子下标大于等于箱子个数时为止。

```public int maxBoxesInWarehouse(int[] boxes, int[] warehouse) {
int[] leftMinHeight = new int[warehouse.length]; // 统计仓库当前位置到入口间的最小高度
for(int i=0;i<warehouse.length;i++){ // 循环仓库每个位置
if(i==0) leftMinHeight[i]=warehouse[i]; // 如果下标为0，最小高度为当前高度
// 否则最小高度为当前高度与前移最小高度的最小值
else leftMinHeight[i]=Math.min(leftMinHeight[i-1],warehouse[i]);
}
Arrays.sort(boxes); // 箱子按照高度排序
int res=0; // 返回结果
int boxIndex=0; // 箱子下标
int houseIndex=leftMinHeight.length-1; // 仓库下标
while(boxIndex<boxes.length&&houseIndex>=0){
// 如果箱子可以移动到当前位置
if(boxes[boxIndex]<=leftMinHeight[houseIndex]){
res++; // 返回结果加一
boxIndex++; // 箱子下标加一（继续放下一个箱子）
houseIndex--; // 仓库下标减一（继续从当前位置左边开始尝试放箱子）
}else{ // 无法移动到当前位置
houseIndex--; // 仓库下标减一（继续从当前位置左边开始尝试放箱子）
}
}
return res;
}```

Runtime: 16 ms, faster than 100.00% of Java online submissions for Put Boxes Into the Warehouse I.

Memory Usage: 52.7 MB, less than 100.00% of Java online submissions for Put Boxes Into the Warehouse I.

```fun maxBoxesInWarehouse(boxes: IntArray, warehouse: IntArray): Int {
var leftMinHeight = mutableListOf<Int>()
for(i in 0..(warehouse.size-1)){
if(i==0)
warehouse[0]
else
Math.min(warehouse[i],leftMinHeight[i-1]))
}
Arrays.sort(boxes);
var res = 0
var indexBox = 0
var indexHouse = warehouse.size-1
while(indexHouse>=0&&indexBox<leftMinHeight.size){
if(boxes[indexBox]<=leftMinHeight[indexHouse]){
res++
indexBox++
indexHouse--
}else{
indexHouse--
}
}
return res;
}```