1760. 袋子里最少数目的球

这是第228场周赛的第三道题，当时没有思路，后来看了一下题解，才知道应该使用二分法来做。

题意求最小化最大开销，类似这样的求最大化最小值、最小化最大值等都可以用二分搜索解决。

具体思路如下：

1. 先大致确定一个左右边界，这里，袋不可能为空，所以左边界是1，右边界也不会大于当前球最多的袋种球的数目，所以右边界是球最多的袋中球的个数。
2. 然后在左右边界中，取中间值middle，验证是否满足条件，根据该结果，确定新的查找区间。
3. 知道左右边界聚拢到同一个值时，该值就是当前的最优解。

二分法需要注意的一点是，区间如何缩减。比如，当前寻找的是最小值，左边界是left，右边界是right。如果middle处满足要求的话，新的右边界应该是middle，而不应该是middle-1，因为我们不知道middle-1处是否满足要求，middle处可能就是最小值；如果middle处不满足要求，那么新的左边界是middle+1，因为我们已经知道middle不满足要求了，如果这里左边界缩到middle，就存在死循环的问题，可能会一直在反复验证middle处是否符合要求。

代码为：

class Solution {
private:
    // 验证是否存在分割方式满足当前开销
    bool check (int spend, vector<int>& nums, int maxOperations){
        int operations = 0;
        for(int n : nums){
            if(n > spend){
                if(n % spend > 0) operations++;
                operations += (n / spend - 1);
            }
        }
        if(operations <= maxOperations) return true;
        else return false;
    }

public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        // 确定二分的左右边界，左边界是最小值，右边界是当前数组里的最大值
        int left = 1, right = INT_MIN;
        for(int n : nums){
            if(n > right) right = n;
        }
        while(right > left){
            // cout << left << "," << right << endl; 
            int middle = (right + left) / 2;
            if(check(middle, nums, maxOperations)){
                right = middle;
            }
            else{
                left = middle+1;
            }
        }
        return right;
    }
};

1552. 两球之间的磁力

本题比1760题稍微难一些，主要是难在check函数不像1760题可以直接得到value值是否成立，而是只能得到，存在最小磁力大于等于value。但由于是对最小值进行最大化，假设真正的最大化的最小值是a，当前证明了b (b < a) 成立，则根据二分法仍会不断向右搜索，找到真正的最大化的最小值a，而且此时确定最小磁力大于等于a，且最小磁力不大于等于a+1，故此时最大化的最小值一定为a。

class Solution {
private:
    // 检验是否存在最小磁力不小于value的情况？
    bool check (vector<int>& position, int m, int value){
        bool flag = false;
        int count = 0;
        for(int i = 1; i < position.size(); i++){
            count += (position[i] - position[i-1]);
            if(count >= value){
                m--;
                count = 0;
                if(m == 1) break;
            }
        }
        return m == 1;
    }
public:
    int maxDistance(vector<int>& position, int m) {
        int left = 1, right = INT_MAX, size = position.size();
        // 先排序
        sort(position.begin(), position.end());
        right = position[size-1];
        int _left = left-1, _right = right+1;
        // 这里用左右边界是否继续改变作为循环结束的标志。
        while(left != _left && right != _right){
            cout << "left: " << left << ", right: " << right << endl;
            int middle = (left + right) / 2;
            if(check(position, m, middle)){
                _left = left;
                left = middle+1;
            }
            else{
                _right = right;
                right = middle - 1;
            }
        }
        return right;
    }
};

利用C++的数据结构set

利用C++的set数据结构，可以维护一个有序的二叉搜索树，从而实现插、查、删的时间复杂度均为O(logn)。

363. 矩形区域不超过 K 的最大数值和

由于数据规模较小，本题使用暴力解法也能解决，时间复杂度为 $O(n^4)$。题解采用的方法是，给矩阵设定一个上边界 $m_1$ 和一个下边界 $m_2$ 在这两个边界内，有n个列，每一列都有一个和。

这些和构成一个数组：$a_0, a_1, a_2, …, a_{n-1}$，$S_i$ 表示这个数组的前缀和，$S_i = \sum_{i=0}^{i-1}a_i$，所以，其中某个矩阵的和，就可以写成：$S_r - S_l$。

$S_r - S_l$ 满足 $S_r - S_l \le k$，或者说是，$S_l \ge S_r - k$ 也就是说，可以将 $S_i$ 存储在一个有序结构中（例如，set），然后在logn的时间复杂度内，可以找到大于等于 $S_r - k$ 的最小值，这个值就可能是我们要找的最优解。

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int res = INT_MIN;
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; i++){ // 确定上界
            vector<int> csum (n , 0);
            for(int j = i; j < m; j++){ // 确定下界
                // 存放前缀和
                vector<int> prefixsum(n+1, 0);
                // 维护一个有序的结构
                multiset<int> mst;
                mst.insert(prefixsum[0]);
                // 增加元素O(n)
                // 往有序的结构里存放prefixsum复杂度是O(nlogn)
                for(int l = 0; l < n; l++){
                    csum[l] += matrix[j][l];
                    if(l == 0) prefixsum[l+1] = csum[l];
                    else prefixsum[l+1] = prefixsum[l] + csum[l];
                    // 在mst中找，大于等于S_r-K的最小值
                    auto find = mst.lower_bound(prefixsum[l+1]-k);
                    if(find != mst.end()){
                        // 求S_r-K
                        int temp = prefixsum[l+1] - *find;
                        if(temp == k) return k;
                        if(temp > res) res = temp;
                    }
                    // 把S_r存到set中
                    mst.insert(prefixsum[l+1]);
                }
            }
        }
        return res;
    }
};