1040. 移动石子直到连续 II

题目链接：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)\)，主要为排序时栈开销。