Easy

题目描述

给你一个整数数组 capacity，其中 capacity[i] 表示第 i 个盒子的容量，以及一个表示物品大小的整数 itemSize。

如果 capacity[i] >= itemSize，那么第 i 个盒子可以存储该物品。

返回一个整数，表示能够存储该物品的最小容量盒子的索引。如果存在多个这样的盒子，返回最小的索引。

如果没有盒子能够存储该物品，返回 -1。

示例 1：

输入：capacity = [1,5,3,7], itemSize = 3
输出：2
解释：索引 2 处的盒子容量为 3，这是能够存储该物品的最小容量。因此答案是 2。

示例 2：

输入：capacity = [3,5,4,3], itemSize = 2
输出：0
解释：能够存储该物品的最小容量是 3，它出现在索引 0 和 3。因此答案是 0。

示例 3：

输入：capacity = [4], itemSize = 5
输出：-1
解释：没有盒子有足够的容量来存储该物品，所以答案是 -1。

约束条件：

  • 1 <= capacity.length <= 100
  • 1 <= capacity[i] <= 100
  • 1 <= itemSize <= 100

解题思路

这道题的核心思路是找到能够装下物品的最小容量盒子，如果有多个相同容量的盒子，选择索引最小的。

解法分析：

方法一：一次遍历法（推荐）

  • 遍历整个数组，维护两个变量：最小有效容量和对应的索引
  • 对于每个盒子，如果容量大于等于物品大小且小于当前记录的最小容量，则更新记录
  • 如果容量等于当前记录的最小容量但索引更小，也需要更新（虽然这种情况在单次遍历中不会发生）
  • 时间复杂度O(n)，空间复杂度O(1)

方法二：两次遍历法

  • 第一次遍历找出所有能装下物品的盒子中的最小容量
  • 第二次遍历找出具有该最小容量的最小索引
  • 时间复杂度O(n)，空间复杂度O(1)

由于题目数据规模较小，两种方法性能相近，但一次遍历法更简洁高效。

代码实现

class Solution {
public:
    int minimumIndex(vector<int>& capacity, int itemSize) {
        int minCapacity = INT_MAX;
        int result = -1;
        
        for (int i = 0; i < capacity.size(); i++) {
            if (capacity[i] >= itemSize && capacity[i] < minCapacity) {
                minCapacity = capacity[i];
                result = i;
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumIndex(self, capacity: list[int], itemSize: int) -> int:
        min_capacity = float('inf')
        result = -1
        
        for i, cap in enumerate(capacity):
            if cap >= itemSize and cap < min_capacity:
                min_capacity = cap
                result = i
        
        return result

public class Solution {
    public int MinimumIndex(int[] capacity, int itemSize) {
        int minCapacity = int.MaxValue;
        int result = -1;
        
        for (int i = 0; i < capacity.Length; i++) {
            if (capacity[i] >= itemSize && capacity[i] < minCapacity) {
                minCapacity = capacity[i];
                result = i;
            }
        }
        
        return result;
    }
}

var minimumIndex = function(capacity, itemSize) {
    let minCapacity = Infinity;
    let result = -1;
    
    for (let i = 0; i < capacity.length; i++) {
        if (capacity[i] >= itemSize && capacity[i] < minCapacity) {
            minCapacity = capacity[i];
            result = i;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 是盒子数组的长度。算法只需要遍历一次数组，使用常数额外空间。