Medium

题目描述

在 X 轴上有一些石子，它们的位置用整数数组 stones 表示。

如果一个石子的位置是最小值或最大值，那么该石子被称为 端点石子 。

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

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

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

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

示例 1：

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

示例 2：

输入：stones = [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 中的值都不相同。

解题思路

这道题需要分别计算最小移动次数和最大移动次数。

最小移动次数： 我们使用滑动窗口思想。对于长度为 n 的石子数组，最终目标是让所有石子连续排列。因此我们需要找到一个长度为 n 的连续区间，使得该区间内已有的石子数量最多，这样需要移动的石子数量就最少。

特殊情况：如果前 n-1 个石子已经连续，且最后一个石子与它们有间隙，此时需要移动 2 次（先移动中间的端点，再移动最后的端点）。

最大移动次数： 要实现最大移动次数，我们应该每次只填补一个空隙。最优策略是保留较小的那个端点间隙（左端间隙或右端间隙），填补较大的间隙，这样能获得更多的移动次数。

左端间隙：stones[n-1] - stones[1] - (n-2) （最右石子到第二个石子之间的空隙数） 右端间隙：stones[n-2] - stones[0] - (n-2) （倒数第二个石子到最左石子之间的空隙数）

最大移动次数 = max(左端间隙, 右端间隙)

代码实现

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        
        // 计算最大移动次数
        int maxMoves = max(stones[n-1] - stones[1] - n + 2, 
                          stones[n-2] - stones[0] - n + 2);
        
        // 计算最小移动次数
        int minMoves = n;
        int j = 0;
        for (int i = 0; i < n; i++) {
            // 找到窗口 [stones[i], stones[i] + n - 1] 内的石子数量
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                j++;
            }
            int alreadyInside = j - i;
            
            // 特殊情况：前n-1个石子连续，最后一个石子单独
            if (alreadyInside == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = min(minMoves, 2);
            } else {
                minMoves = min(minMoves, n - alreadyInside);
            }
        }
        
        return {minMoves, maxMoves};
    }
};

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[-2] - stones[0] - n + 2)
        
        # 计算最小移动次数
        min_moves = n
        j = 0
        for i in range(n):
            # 找到窗口 [stones[i], stones[i] + n - 1] 内的石子数量
            while j < n and stones[j] - stones[i] + 1 <= n:
                j += 1
            already_inside = j - i
            
            # 特殊情况：前n-1个石子连续，最后一个石子单独
            if already_inside == n - 1 and stones[j-1] - stones[i] + 1 == n - 1:
                min_moves = min(min_moves, 2)
            else:
                min_moves = min(min_moves, n - already_inside)
        
        return [min_moves, max_moves]

public class Solution {
    public int[] NumMovesStonesII(int[] stones) {
        Array.Sort(stones);
        int n = stones.Length;
        
        // 计算最大移动次数
        int maxMoves = Math.Max(stones[n-1] - stones[1] - n + 2,
                               stones[n-2] - stones[0] - n + 2);
        
        // 计算最小移动次数
        int minMoves = n;
        int j = 0;
        for (int i = 0; i < n; i++) {
            // 找到窗口 [stones[i], stones[i] + n - 1] 内的石子数量
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                j++;
            }
            int alreadyInside = j - i;
            
            // 特殊情况：前n-1个石子连续，最后一个石子单独
            if (alreadyInside == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                minMoves = Math.Min(minMoves, 2);
            } else {
                minMoves = Math.Min(minMoves, n - alreadyInside);
            }
        }
        
        return new int[] {minMoves, maxMoves};
    }
}

var numMovesStonesII = function(stones) {
    stones.sort((a, b) => a - b);
    const n = stones.length;
    
    // Maximum moves
    const maxMoves = Math.max(
        stones[n-1] - stones[1] - n + 2,
        stones[n-2] - stones[0] - n + 2
    );
    
    // Minimum moves
    let minMoves = n;
    let j = 0;
    
    for (let i = 0; i < n; i++) {
        while (j < n && stones[j] - stones[i] < n) {
            j++;
        }
        
        const stonesInRange = j - i;
        
        if (stonesInRange == n - 1 && stones[j-1] - stones[i] == n - 2) {
            minMoves = Math.min(minMoves, 2);
        } else {
            minMoves = Math.min(minMoves, n - stonesInRange);
        }
    }
    
    return [minMoves, maxMoves];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(1)
  • 时间复杂度：O(n log n)，主要来自排序操作，滑动窗口部分是 O(n)
  • 空间复杂度：O(1)，只使用常数额外空间

相关题目