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

这道题到底在问什么

输入

stones = [7,4,9]

输出

[1,2]

最优解：一步一步想明白

1. 3记住两句：最大「移一端、丢小端缝、数空格」；最小「滑长 n 窗口、数窗内最多石子、特例留空位算 2 步」。后面每帧都在套它。
2. 4先看原始输入，6 颗石子位置乱序排列。所有套路都建立在「排好序」之上，所以第一步永远是排序。
3. 5排好序后变成 2、3、5、6、8、11。最左是 2、最右是 11，整段从 2 到 11 一共 10 个位置，里面只占了 6 颗。接下来先算最大、再算最小。
4. 6先算最大步数。整段 10 个位置里有 4 个空格。最理想是每一步只填一个空格、慢慢挪。但第一步必须把一个端点往里搬，会放弃它那一侧的端缝，所以要在两种放弃里挑划算的。
5. 7第一种：第一步动最左的 2，等于放弃左端缝，往后所有石子都挤进 3 到 11 这段。这段有 4 个空格，每步填一个，最多走 4 步。
6. 8第二种：第一步动最右的 11，等于放弃右端缝，石子挤进 2 到 8 这段。这段只有 2 个空格，最多走 2 步。
7. 9两种放弃里挑空格多的：4 和 2 取大，最大步数就是 4。直觉上就是「丢掉较小的那条端缝，剩下的空格能填多少步就走多少步」。
8. 10再算最小。终局是 6 个挨着的位置。我们拿一个宽度不超过 6 的窗口在数轴上滑，窗口里已经就位的石子越多，要从外面搬进来的就越少。右指针 j 往右扩，一旦窗口宽度超过 6，左指针 i 就跟着右移。
9. 11右指针扩到位置 2，窗口宽度 1，还在 6 以内，左指针不动。
10. 12窗内已就位 1 颗，外面还有 5 颗要搬进来，本窗需要 5 步。比之前更少，最少刷新成 5。
11. 13右指针扩到位置 3，窗口宽度 2，还在 6 以内，左指针不动。
12. 14窗内已就位 2 颗，外面还有 4 颗要搬进来，本窗需要 4 步。比之前更少，最少刷新成 4。
13. 15右指针扩到位置 5，窗口宽度 4，还在 6 以内，左指针不动。
14. 16窗内已就位 3 颗，外面还有 3 颗要搬进来，本窗需要 3 步。比之前更少，最少刷新成 3。
15. 17右指针扩到位置 6，窗口宽度 5，还在 6 以内，左指针不动。
16. 18窗内已就位 4 颗，外面还有 2 颗要搬进来，本窗需要 2 步。比之前更少，最少刷新成 2。
17. 19右指针扩到位置 8，宽度一度超过 6，左指针往右移了 1 步，缩到位置 3，让窗口宽度回到 6，控制在 6 以内。
18. 20窗内已就位 4 颗，外面还有 2 颗要搬进来，本窗需要 2 步。没比当前最少 2 更优，继续滑。
19. 21右指针扩到位置 11，宽度一度超过 6，左指针往右移了 2 步，缩到位置 6，让窗口宽度回到 6，控制在 6 以内。
20. 22窗内已就位 3 颗，外面还有 3 颗要搬进来，本窗需要 3 步。没比当前最少 2 更优，继续滑。
21. 23滑完一遍，最划算的窗口已就位 4 颗，只要再搬 2 颗，最少就是 2 步。配上前面算的最大 4 步，主例答案是 [2, 4]。
22. 24单独看这个最容易错的特例：1、2、3、4 已经连成一片，只有 9 落在远处。窗口里能装下 4 颗连续石子，看着像只差 1 颗、1 步就完事，真的吗？
23. 25朴素地套公式：窗口里有 4 颗，n 是 5，5 减 4 等于 1，好像 1 步就行。问题出在这个 1 步根本走不通，下一帧看为什么。
24. 26想 1 步收尾，只能把端点 9 挪到位置 5，凑成 1、2、3、4、5。可规则要求端点挪完不能还是端点，而 5 恰好是新的最右端，这步违规。所以 1 步走不通。
25. 27正确走法要 2 步：先把最左的 1 挪到 6，变成 2、3、4、6、9；再把端点 9 挪到 5，凑成 2、3、4、5、6 连续收工。所以「n-1 已连续、只差一个空位、最后一颗在远处」这个特例，最少是 2 步，公式里要单独判它。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

#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};
    }
};

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};
    }
}

复杂度

面试官可能追问