题目链接：1040. 移动石子直到连续 II
方法：找规律
解题思路
参考—【图解】下跳棋
代码
class Solution {
public:
vector<int> numMovesStonesII(vector<int>& stones) {
sort(stones.begin(), stones.end());
int n = stones.size();
int e1 = stones[n - 1] - stones[1] - n + 2;
int e2 = stones[n - 2] - stones[0] - n + 2;
int max_move = max(e1, e2);
if (!e1 || !e2) {
return {min(2, max_move), max_move};
}
int l = 0, max_cnt = 0;
for (int r = 0; r < n; r ++ ) {
while (stones[r] - stones[l] + 1 > n) l ++ ;
max_cnt = max(max_cnt, r - l + 1);
}
return {n - max_cnt, max_move};
}
};
复杂度分析
时间复杂度：\(O(nlogn)\)；
空间复杂度：\(O(logn)\)，主要为排序时栈开销。