1040. 移动石子直到连续 II 在一个长度 无限 的数轴上，第 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 这样的移动来结束游戏，因为这是不合要求的移动。

提示：

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

Solutions

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        int a1 = stones[n - 2] - stones[0] + 1 - (n - 1);
        int a2 = stones[n - 1] - stones[1] + 1 - (n - 1);
        int maxMove = Math.max(a1, a2);
        if (a1 == 0 || a2 == 0) { //0 ~ n - 2或 1 ~ n - 1全部相连
            //剩下一个离相连区域的距离为maxMove
            //如果距离为 1或0， 则最小移动次数为1或不用移动0， 否则为 2
            return new int[]{Math.min(maxMove, 2), maxMove};
        }

        //大小为n的滑动窗口中， 最多包含多少个石子
        //以stone[l]为开头，以stone[r - 1]结尾，
        //则[l, r)的窗口大小为stones[r - 1] - stones[l] + 1, 石子总数为 r - l
        //为确保上述窗口大小在n内, 先判断一下stones[r] - stones[l] + 1是否小于等于n
        int maxWindowsStones = 0;
        int r = 0;
        int l = 0;
        while (r < n) {
            while (r < n && stones[r] - stones[l] + 1 <= n) {
                r++;
            }

            maxWindowsStones = Math.max(r - l, maxWindowsStones);
            l++;
        }

        return new int[]{n - maxWindowsStones, maxMove};
    }
}

Ideas

• 由题意可知，每进行一轮操作，石子的左右端点的距离会缩短，一轮一轮收敛。最后会石子都紧邻游戏结束。

  举个例子：

  初始时有 8 颗石子，在数轴上的有石子的刻度为：

  4，6，8，9，15，16，19，20

  最大值求解方法：

  石子可以放置的空间，等于左右两端石子之间的未占用位置。在例子中，一共有 20-4+1-8 个位置。

  石子覆盖的线段长度是 20-4 个，加上一个端点的位置即 20-4+1，再减去已经占用的 8 个位置。

  用公式表示为：s1=stones[n−1]−stones[0]+1−n。

  但是第一次移动的左端点或右端点的石子后，这个移动的石子和它相邻的那颗石子之间的空间，后面就不能被放置了，因为与他相邻的那个点变为端点，他们之间的位置不可以被放置了。

  例如第一步移动了 4，那么 5 这个位置就不可能放置石子了。所以要计算不能被访问的空间s2=min(stones[n−1]−stones[n−2]−1,stones[1]−stones[0]−1)。

  最大值为 s1-s2。因为在后面的步骤里，我们都可以做出策略，让每一轮左右端点的差值只减 1。

  最小值求解方法：

  如果最后游戏结束，那么一定有 n 个连续坐标摆满了石子。如果我们要移动最少，必定要找一个石子序列，使得在 n 大小连续的坐标内，初始时有最多的石子。

  设想有个尺子，上面有 n 个刻度点，我们用这个尺子在石子从最左边到最右边移动，每动一次都查看下在尺子范围内有 m 个石子，那么要使这个区间填满，就需要移动 n−m 次。

  只要在尺子外部有石子，就有策略填满尺子内的。

  这些次数中最小的就为虽少次数。

  但是有一种特例： 1，2，3，4，7

  这种 1-4 是最好的序列，但是 7 不能移动到端点，只能 1 先移动到 6，然后 7 移动到 5 解决，这种情况要用 2 步。就是尺子内的石子都是连续的，中间没空洞，只在边上有空，要用 2 次。