20250212力扣每日一题

知识点

寻找数组中最大的元素
- max_element(nums.begin(), nums.end())返回的是迭代器
- *操作符解引用了迭代器，直接获取了元素

int findMax(vector<int> &num){
    MaxElement = *max_element(nums.begin(), nums.end());
    return MaxElement;
}

解题思路

理解题意，将题目中的要求转化为：
- 给定maxOperations操作次数，能否可以将单个袋子中球数目的最大值不超过y
假设$y = y_0$满足条件，那么所有$y > y_0$肯定都符合条件，我们要找出一个$y_{optimal}$，使得所有$y \geq y_{optimal}$符合条件，所有$y < y_{optimal}$不符合条件
可以考虑使用二分查找$y_{opt}$
初始化left = 1, right = *max_element(nums.begin(), nums.end())
判断每个袋子中的球数需要的操作数，使用下列公式进行计算，该公式含义为：
- 当nums[i] <= y时，操作数为0
- 当y < nums[i] <= 2y时，操作数为1
- 当2y < nums[i] <= 3y时，操作数为2
- ……

\[\left\lfloor \frac{\text{nums}[i] - 1}{y} \right\rfloor\]

遍历nums中的所有元素，获取预期操作数
如果操作数大于maxOperations，则说明y较小，left = y + 1，说明所有小于等于当前y值都不行
如果操作数小于maxOperations，则说明y较大，right = y - 1，我们继续寻找有没有符合条件的更小的y值
直至left > right，我们获得y值就是符合这两个条件的

实现代码

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int ans = 0;
        while(left <= right){
            int y = (left + right) / 2;
            long long ops = 0;
            for(int x: nums){
                ops += (x - 1) / y;
            }
            if(ops <= maxOperations){
                ans = y;
                right = y - 1;
            }else{
                left = y + 1;
            }
        }

        return ans;
    }
};

知识点

解题思路

实现代码

Enjoy Reading This Article?