移动石子直到连续 II

难度: Medium

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

Submission

运行时间: 46 ms

内存: 17.0 MB

from typing import List

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()  # 先对石子位置进行排序
        n = len(stones)
        max_moves = max(stones[-1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)  # 计算最大移动次数
        
        # 计算最小移动次数
        i = 0
        j = 0
        min_moves = n  # 初始化最小移动次数为石子数量
        while i < n:
            while stones[i] - stones[j] >= n:
                j += 1
            if i - j + 1 == n - 1 and stones[i] - stones[j] == n - 2:
                min_moves = min(min_moves, 2)  # 特殊情况，如 [1,2,5]
            else:
                min_moves = min(min_moves, n - (i - j + 1))
            i += 1
        
        return [min_moves, max_moves]

# 示例测试
solution = Solution()
print(solution.numMovesStonesII([7, 4, 9]))  # 输出: [1, 2]
print(solution.numMovesStonesII([6, 5, 4, 3, 10]))  # 输出: [2, 3]
print(solution.numMovesStonesII([100, 101, 104, 102, 103]))  # 输出: [0, 0]

Explain

首先对石子的位置进行排序，然后分别计算最大移动次数和最小移动次数。最大移动次数是将所有石子移动到一端所需的最大移动次数，可以通过将除了最左端或最右端的石子外的所有石子移动到另一端来实现。最小移动次数的计算稍微复杂一些，需要考虑连续的石子的位置，使用滑动窗口的方法来计算可以放置最多石子的区间，然后根据这个区间来确定最小的移动次数。

时间复杂度: O(n log n)

空间复杂度: O(1)

from typing import List

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()  # 先对石子位置进行排序
        n = len(stones)
        max_moves = max(stones[-1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)  # 计算最大移动次数
        
        # 计算最小移动次数
        i = 0
        j = 0
        min_moves = n  # 初始化最小移动次数为石子数量
        while i < n:
            while stones[i] - stones[j] >= n:
                j += 1
            if i - j + 1 == n - 1 and stones[i] - stones[j] == n - 2:
                min_moves = min(min_moves, 2)  # 特殊情况，如 [1,2,5]
            else:
                min_moves = min(min_moves, n - (i - j + 1))
            i += 1
        
        return [min_moves, max_moves]

# 示例测试
solution = Solution()
print(solution.numMovesStonesII([7, 4, 9]))  # 输出: [1, 2]
print(solution.numMovesStonesII([6, 5, 4, 3, 10]))  # 输出: [2, 3]
print(solution.numMovesStonesII([100, 101, 104, 102, 103]))  # 输出: [0, 0]

Explore

这两个公式用于计算将所有石子移动到一端所需的最大移动次数。公式`stones[-1] - stones[1] - n + 2`表示将除最右端石子外的所有石子移动到左端所需的最大移动次数，计算方式是取最右端石子与第二个石子之间的距离，减去除第一个和最后一个石子外的石子数量，再加上2。这是因为我们需要将这段距离变为连续的，每次移动可以将一个石子放在当前最远的石子旁边。同理，公式`stones[n - 2] - stones[0] - n + 2`表示将除最左端石子外的所有石子移动到右端所需的最大移动次数，计算方式相似，只是从另一端进行。

滑动窗口方法用于找到一段最长的连续区间，这个区间内最多可以放置石子。通过计算这样的区间，可以确定需要最小移动次数，以使所有石子连续。在滑动窗口中，我们会尝试将窗口扩展到最大，使得窗口内的石子尽可能多，同时窗口的长度不超过石子总数。这样，窗口外剩余的石子数量就是至少需要移动的次数。这种方法有效地帮助我们找到最优移动策略，确保石子数量最大化地使用给定的空间。

当`i - j + 1 == n - 1`且`stones[i] - stones[j] == n - 2`时，意味着除一个石子外，所有石子几乎形成了一个连续序列，但是有一个长度为2的空隙。在这种情况下，我们无法通过一步移动来填补这个空隙，因此最小移动次数设置为2。具体的移动步骤通常是将两端中的一个石子移动到这个空隙中的一端，然后将另一个石子移动到空隙的另一端，或者根据具体位置可能需要将一端的石子依次移动来填补这个空隙。这样的操作确保所有石子都能连续排列。