3861. 容量最小的箱子

题目描述

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

如果第 i 个箱子的容量满足 capacity[i] >= itemSize，那么该箱子可以存放该物品。

要求返回可以存放该物品的容量最小的箱子的下标。如果有多个这样的箱子，返回下标最小的一个。

如果没有任何箱子可以存放该物品，则返回 -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 更小，因此答案是 0。

示例 3：

输入： capacity = [4], itemSize = 5

输出： -1

解释：

没有任何箱子的容量足够存放该物品，因此答案是 -1。

提示：

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

解法

方法一：一次遍历

我们初始化一个变量 \(\textit{ans}\)，表示可以存放该物品的容量最小的箱子的下标，初始值为 \(-1\)。我们遍历数组 \(\textit{capacity}\)，对于每个箱子，如果它的容量大于等于 \(\textit{itemSize}\)，则说明它可以存放该物品。此时，我们需要判断它是否是目前为止容量最小的箱子，如果是，则更新 \(\textit{ans}\) 的值。最后返回 \(\textit{ans}\) 即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{capacity}\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def minimumIndex(self, capacity: list[int], itemSize: int) -> int:
        ans = -1
        for i, x in enumerate(capacity):
            if x >= itemSize and (ans == -1 or x < capacity[ans]):
                ans = i
        return ans

class Solution {
    public int minimumIndex(int[] capacity, int itemSize) {
        int ans = -1;
        for (int i = 0; i < capacity.length; ++i) {
            int x = capacity[i];
            if (x >= itemSize && (ans == -1 || x < capacity[ans])) {
                ans = i;
            }
        }
        return ans;
    }
}

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

func minimumIndex(capacity []int, itemSize int) int {
    ans := -1
    for i, x := range capacity {
        if x >= itemSize && (ans == -1 || x < capacity[ans]) {
            ans = i
        }
    }
    return ans
}

function minimumIndex(capacity: number[], itemSize: number): number {
    let ans = -1;
    for (let i = 0; i < capacity.length; ++i) {
        const x = capacity[i];
        if (x >= itemSize && (ans === -1 || x < capacity[ans])) {
            ans = i;
        }
    }
    return ans;
}

3861. 容量最小的箱子

题目描述

解法

方法一：一次遍历

评论