What is the main strategy for Moving Stones Until Consecutive II?

Sort the stones and use a sliding window to compute minimal moves while calculating gaps at endpoints for maximum moves.

How do I handle edge cases in the sliding window approach?

Specially check if only one stone is outside the ideal window; this often requires two moves instead of one.

Can stones be moved anywhere or only endpoints?

Moves are restricted to endpoint stones. Moving non-endpoints is not allowed and breaks the rules.

What is the time complexity of this solution?

Sorting takes O(N log N), sliding window minimum is O(N), and maximum moves calculation is O(1) after sorting.

Why is the problem categorized under sliding window with running state updates?

Because minimal moves rely on counting stones within moving windows and updating state dynamically as the window shifts.

#1040

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

移动石子直到连续 II

在 X 轴上有一些不同位置的石子。给定一个整数数组 stones 表示石子的位置。如果一个石子在最小或最大的位置，称其为端点石子。每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。值得注意的是，如果石子像 stones = [1,2,5] 这样…

数组数学滑动窗口排序

题目描述

在 X 轴上有一些不同位置的石子。给定一个整数数组 stones 表示石子的位置。

如果一个石子在最小或最大的位置，称其为 端点石子。每个回合，你可以将一颗 端点石子 拿起并移动到一个未占用的位置，使得该石子不再是一颗 端点石子。

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

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

以长度为 2 的数组形式返回答案，其中：

answer[0] 是你可以移动的最小次数
answer[1] 是你可以移动的最大次数。

示例 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 <= stones.length <= 10⁴
1 <= stones[i] <= 10⁹
stones 的值各不相同。

lightbulb

解题思路

方法一：排序 + 分类讨论 + 双指针

我们先对数组 stones 进行升序排序，接下来分别考虑最大移动次数 $mx$ 和最小移动次数 $mi$ 。

对于最大移动次数 $mx$ ：

由于我们每一次只能选择将端点石子移动到未占用且不是端点石子的位置，如果我们选择 stones[0] 作为第一次移动的端点石子，那么从 stones[0] 到 stones[1] 之间的所有未占用的位置都会被跳过，我们可以选择移动到最近的且未占用的位置，接下来每一次都将最左端的石子移动到最近的且未占用的位置，那么最多可以移动的次数为 $stones[n - 1] - stones[1] + 1 - (n - 1)$ ；同理，如果我们选择 stones[n - 1] 作为第一次移动的端点石子，那么最多可以移动的次数为 $stones[n - 2] - stones[0] + 1 - (n - 1)$ 。取两者的最大值即为最大移动次数 $mx$ 。

对于最小移动次数 $mi$ ：

我们用双指针 $i$ 和 $j$ 标识一个窗口的左右端点，若窗口内的位置数 $stones[j] - stones[i] + 1 \gt n$ 时，我们需要缩小窗口，即指针 $i$ 向右移动。如果此时窗口中有连续的 $n-1$ 个石子，即满足 $j - i + 1 = n - 1$ 且 $stones[j] - stones[i] + 1 = n - 1$ ，那么最少需要移动的次数为 $2$ ；否则，我们用 $n$ 减去窗口内的石子数，可以得到最少需要移动的次数，即 $n - (j - i + 1)$ 。取所有情况的最小值即为最小移动次数 $mi$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 stones 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def numMovesStonesII(self, stones: List[int]) -> List[int]:
        stones.sort()
        mi = n = len(stones)
        mx = max(stones[-1] - stones[1] + 1, stones[-2] - stones[0] + 1) - (n - 1)
        i = 0
        for j, x in enumerate(stones):
            while x - stones[i] + 1 > n:
                i += 1
            if j - i + 1 == n - 1 and x - stones[i] == n - 2:
                mi = min(mi, 2)
            else:
                mi = min(mi, n - (j - i + 1))
        return [mi, mx]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if candidate identifies endpoint stones correctly for both min and max calculations.
question_mark
Observes whether sliding window correctly counts stones already in place for minimal moves.
question_mark
Watches for handling edge cases where two moves are needed due to single gaps at ends.

warning

常见陷阱

外企场景

error
Forgetting to handle the special case where exactly one stone is outside a nearly full window.
error
Miscounting maximum moves by not subtracting the largest endpoint gap properly.
error
Assuming consecutive stones start from the first or last position without sorting first.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing the movement rule to allow moving any stone, not just endpoints, affects both min and max computations.
arrow_right_alt
Limiting stone positions to a small range introduces simpler window counting and may reduce complexity.
arrow_right_alt
Extending to 2D positions requires adapting sliding window logic and gap calculations to multiple axes.

help

常见问题

外企场景

继续练习

#1610 可见点的最大数目 #1030 距离顺序排列矩阵单元格 #976 三角形的最大周长