移动石子直到连续 II 图解题解

石子在数轴上挪来挪去，最后要报哪两个数

给一排位置互不相同的石子 stones，每步只能拿起当前最左或最右的端点，放进某个空位，且放完后它不能仍是端点；石子连成一段连续位置即停。返回长度 2 的数组 [最少步数, 最多步数]。以题面 stones=[7,4,9] 为例，排序后 4、7、9，最少 1 步（4 挪到 8 得 7、8、9）、最多 2 步，答案 [1,2]。

为什么不能真的一颗颗搬着去试

最直接的想法是模拟搬端点、穷举每步的放法直到连续。可每步有多个空位、还要递归很多层，移动序列随石子数指数级膨胀，稍大就跑不完。让它变简单的前提是先排序——端点、相邻间距、区间能装几颗，全靠位置有序才能直接读出，所以算最大最小前第一步都是把 stones 排成从小到大。

最大步数：放弃一条端缝，把剩下的空格填满

第一步必然动某个端点，它一旦往里搬，外侧那条通向远处的空隙（端缝）就永久作废。于是只有两种选择：放弃最左，剩下 n-1 颗挤进第二颗到最后一颗的区间；或放弃最右，挤进第一颗到倒数第二颗的区间。哪个区间空位多就能多走几步，取大者即最大步数——参考代码正是数每个区间首尾之间能站几个位置、各减掉 n-1 颗石子。

最小步数：拿一个长 n 的窗口滑过去数石子

终局是 n 颗石子占满 n 个连续位置，所以任何宽度不超过 n 的区间都可能是最后落点。让一个长 n 的滑动窗口贴着石子滑，它是一段宽度不超过 n、从左往右挪的区间：窗内就位的石子越多，要从窗外搬进来的越少，本窗步数就是 n 减窗内石子数。右指针每纳入一颗，宽度一超 n 就把左指针右移、压回 n 以内；每个窗口的『n 减窗内数』取最小即最少步数。

那个『差一点就排好』的位置，公式为什么少算一步

有一种排布会坑这条公式：n-1 颗已连成一片，只剩最后一颗落在远处。窗口罩住那 n-1 颗，按『n 减窗内数』像是只差 1 步，可这步走不通——一步收尾只能把远处那颗端点挪到紧邻空位，而那位置又成了新端点，违反『挪完不能还是端点』。正确要 2 步：先把连续段一端挪出一格，再把远处那颗填进中间。n-1 颗连成片时首尾跨度就是 n-2，所以窗内恰好 n-1 颗、且窗口跨度等于 n-2 时，单独把这窗记成 2 步。

排序后的 4、7、9，最大最小分头验一遍

排序得 4、7、9，n=3。最大：放弃最左 4，两颗挤进 7 到 9 共 3 位装 2 颗、1 空位，1 步；放弃最右 9，挤进 4 到 7 共 4 位装 2 颗、2 空位，2 步，取大得 2。最小：长 3 窗口滑到 7、9（宽度 9-7+1=3 没超 n），窗里 2 颗只需搬 4，1 步；跨度 9-7=2 不等于 n-2=1，没踩特例按 3-2=1 记。答案 [1,2]。

不排序、漏减 n-1、忘判特例，答案就偏了

不排序直接套公式最隐蔽：端点、间距、窗口宽度全依赖有序位置，乱序算的量不可信。算最大若只算一侧、或忘末尾减 n-1，会漏掉『放弃较小端缝更划算』的走法。算最小若漏掉那个『n-1 已连续、差一空位、最后一颗在远处』的特例，会把 2 步误报成 1 步。石子本就连续时输出 0。排序 O(n log n) 是瓶颈，最大 O(1)、滑窗 O(n)，空间 O(1)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        int mi = n;
        int mx = max(stones[n - 1] - stones[1] + 1, stones[n - 2] - stones[0] + 1) - (n - 1);
        for (int i = 0, j = 0; j < n; ++j) {
            while (stones[j] - stones[i] + 1 > n) {
                ++i;
            }
            if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2) {
                mi = min(mi, 2);
            } else {
                mi = min(mi, n - (j - i + 1));
            }
        }
        return {mi, mx};
    }
};

Java

import java.util.*;
class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        int mi = n;
        int mx = Math.max(stones[n - 1] - stones[1] + 1, stones[n - 2] - stones[0] + 1) - (n - 1);
        for (int i = 0, j = 0; j < n; ++j) {
            while (stones[j] - stones[i] + 1 > n) {
                ++i;
            }
            if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2) {
                mi = Math.min(mi, 2);
            } else {
                mi = Math.min(mi, n - (j - i + 1));
            }
        }
        return new int[] {mi, mx};
    }
}