给定两个正整数数组 boxes 和 warehouse ,分别包含单位宽度的箱子的高度,以及仓库中 n 个房间各自的高度。
仓库的房间分别从 0 到 n - 1 自左向右编号, warehousei (索引从 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 的箱子。
示例 4:
输入:boxes = [4,5,6], warehouse = [3,3,3,3,3]
输出:0
提示:
n == warehouse.length
1 <= boxes.length, warehouse.length <= 10^5
1 <= boxes[i], warehouse[i] <= 10^9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/put-boxes-into-the-warehouse-i 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:LeetCode 1580. 把箱子放进仓库里 II(排序)
class Solution {
public:
int maxBoxesInWarehouse(vector<int>& boxes, vector<int>& warehouse) {
int MIN = warehouse[0];
for(int i = 1; i < warehouse.size(); ++i)
{
MIN = min(MIN, warehouse[i]);
warehouse[i] = MIN;//有效的高度
}
sort(boxes.rbegin(), boxes.rend());
int ans = 0, i = boxes.size()-1, j = warehouse.size()-1;
while(i>=0 && j>=0)
{
if(boxes[i] <= warehouse[j])
{ // 能放进去
ans++;
i--,j--;
}
else
j--;//放不进去,换下一个可能的更高的仓库
}
return ans;
}
};
112 ms 59 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!