Leetcode 1552. 两球之间的磁力

题目

Leetcode 1552. 两球之间的磁力

代码（9.17 首刷看解析）

滴滴9.15笔试题

class Solution {
public:
    bool check(int x, vector<int>& position, int m) {
        int pre = position[0], cnt = 1;
        for(int i = 1; i < position.size(); ++i) {
            if(position[i] - pre >= x) {    // 累计可以放下球的个数
                pre = position[i];
                cnt += 1;
            }
        }
        return cnt >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1, right = position.back()-position[0], ans = -1;
        while(left <= right) {
            int mid = (left+right)/2;
            if(check(mid, position, m)) {   // 若放得下m个球，增大球间距
                ans = mid;
                left = mid+1;
            } else {    // 若放不下则减少球间距
                right = mid -1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27