题目描述

在一个长度无限的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作端点石子。

每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。

值得注意的是，如果石子像 stones = [1,2,5] 这样，你将无法移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]。

样例

输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

输入：[100,101,104,102,103]
输出：[0,0]

限制

• 3 <= stones.length <= 10^4
• 1 <= stones[i] <= 10^9
• stones[i] 的值各不相同。

算法

(贪心，双指针) $O(n \log n)$

1. 显然现将数组从小到大排序，然后分别求最小和最大移动次数。
2. 最小移动次数
   • 先求出以每个点结尾时，长度为 n 的区间能覆盖到当前最多的石子的数量，记为 m。
   • 例如 [7,4,9] 的最大覆盖长度为 2； [1,7,8,11] 的最大覆盖长度也是 2，[100,101,104,102,103] 的最大覆盖长度为 5。
   • 这一步可以通过双指针来求得。
   • 如果 m 不等于 n - 1，则我们可以通过 n - m 次移动得到答案，这已经达到了答案的下限。
     • m 等于 n，答案为 0；
     • m < n - 1，有可能是两个端点不在这个区间内，也有可能是一端至少两个点不在区间内。这两种情况都可以通过贪心的移动，组成最后连续的区间。
   • 如果 m 等于 n - 1
     • stones[0] + n - 1 == stones[n - 2] 或者 stones[1] + n - 1 == stones[n - 1]。这两种情况可以通过一步完成，例如 [3,5,6,7,8]，[5,6,7,8,10]。
     • 其他情况，都需要 2 步完成。
3. 最大移动次数
   • 累计所有两个相邻石子的（距离减一），记为 sum。
   • sum 减去开头两个石子（距离减一）或者末尾两个石子（距离减一）的最小值。
   • 因为第一次移动会直接将开头或者末尾的石子与相邻的石子合并在一起。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，求最大最小值的时间复杂度为 $O(n)$。
• 故最终的时间复杂度为 $O(n \log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int solve_min(const vector<int>& stones) {
        int n = stones.size();
        int m = 0;

        for (int l = 0, r = 0; r < n; r++) {
            while (stones[r] - stones[l] >= n)
                l++;
            m = max(m, r - l + 1);
        }

        if (m == n - 1) {
            if (stones[0] + n - 1 == stones[n - 2]
               || stones[1] + n - 1 == stones[n - 1])
                return 1;

            return 2;
        }

        return n - m;
    }

    int solve_max(const vector<int>& stones) {
        int n = stones.size();
        int sum = 0;

        for (int i = 0; i < n - 1; i++)
            sum += stones[i + 1] - stones[i] - 1;

        sum -= min(stones[1] - stones[0] - 1, 
                   stones[n - 1] - stones[n - 2] - 1);

        return sum;
    }

    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        return {solve_min(stones), solve_max(stones)};
    }
};